求1到n里面约数最多的数的约数个数

曾经终败给现在 2022-05-28 07:18 215阅读 0赞

题目:求1到n里面约数最多的数的约数个数

分析:首先明白一个数的约数的求法。

根据约数和定理:对于一个大于1正整数n可以[分解质因数][Link 1]：n=p1^a1\*p2^a2\*p3^a3\*…\*pk^ak,则由[约数个数定理][Link 2]可知n的正约数有(a₁+1)(a₂+1)(a₃+1)…(ak+1)个，

暴力算出每一个数的约数的个数，超时！

根据唯一分解定理，我们知道每一个数都可以用质因子的积表示，而约数的个数只与指数有关！

我们知道pn>...>p3>p2>p1，那么假设我们存在某一个ak>a1 那么我们交换pk与p1的指数，显然约数个数不变，但是数变小了！！！

也就是说对于任何n,m如果pn>pm那么an<am 要好一些，是不是最优的，不确定！但是在已经为我们淘汰了许多了。

我们枚举每一个质因子的质数，保证其指数递减。

代码如下:

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    
    int p[20] = {0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,51};
    ll ans,n;
    
    void dfs(int pos,ll num,ll sum,int len)//当前枚举p的位置，约数个数，数sum,前一个质因子的指数最大值
    {
        if (sum>n) return ;
        if (sum<=n) ans=max(ans,num);
        for (int i=1;i<=len;i++) {
            ll res=pow(p[pos],i);
            if (sum>n/res) break;//注意不要用sum*res>n，炸long long
            dfs(pos+1,num*(i+1),sum*(res),i);
        }
    }
    int main()
    {
        cin>>n;
        ans=0;
        dfs(1,1,1,30);
        cout<<ans<<endl;
        return 0;
    }

[Link 1]: https://baike.baidu.com/item/%E5%88%86%E8%A7%A3%E8%B4%A8%E5%9B%A0%E6%95%B0
[Link 2]: https://baike.baidu.com/item/%E7%BA%A6%E6%95%B0%E4%B8%AA%E6%95%B0%E5%AE%9A%E7%90%86

发表评论取消回复

表情：

评论列表（有 0 条评论，215人围观）

还没有评论，来说两句吧...

相关阅读

相关试除法求约数

试除法求约数给定 n 个正整数 ai，对于每个整数 ai，请你按照从小到大的顺序输出它的所有约数。输入格式第一行包含整数 n。接下来 n 行，每行包含一个

偏执的太偏执、/ 2024年03月31日 13:47/ 0 赞/ 106 阅读

相关【约数】魔法数

[K-魔法数\_2022河南萌新联赛第（六）场：郑州大学 (nowcoder.com)][K-_2022_ _nowcoder.com] 题意： ![278611133b2

左手的ㄟ右手/ 2024年03月30日 11:47/ 0 赞/ 100 阅读

相关约数个数(c++, java)

约数个数给定 n 个正整数 ai，请你输出这些数的乘积的约数个数，答案对 109+7 取模。输入格式第一行包含整数 n。接下来 n 行，每行包含一个整

喜欢ヅ旅行/ 2024年03月26日 20:27/ 0 赞/ 100 阅读

相关 n的约数（约数统计+dfs）

链接： [https://www.nowcoder.com/acm/contest/82/A][https_www.nowcoder.com_acm_contest_82_A]

不念不忘少年蓝@/ 2024年02月18日 19:17/ 0 赞/ 85 阅读

相关约数 AcWing 870. 约数个数

约数 AcWing 870. 约数个数原题链接 [AcWing 870. 约数个数][AcWing 870.] 算法标签数学知识约数试除法因式分解

迷南。/ 2023年09月28日 11:38/ 0 赞/ 17 阅读

相关求最多约数个数（暴力破解版VS质因子分解）

质因子分解：质因子分解 n=p1a1+p2a2+...+pnan num=(1+a1)(1+a2)...(1+an) def Prime_f

本是古典何须时尚/ 2022年12月11日 09:25/ 0 赞/ 154 阅读

相关试除法求数的约数

上一篇博客：[分解质因数][Link 1] > 写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果

一时失言乱红尘/ 2022年11月18日 01:26/ 0 赞/ 226 阅读

相关约数个数

Description 给一个整数N(N<=1,000,000,000)，求它的所有约数的个数。 Input 多个N Ou

雨点打透心脏的1/2处/ 2022年09月29日 12:54/ 0 赞/ 178 阅读

相关求1到n里面约数最多的数的约数个数

题目:求1到n里面约数最多的数的约数个数分析:首先明白一个数的约数的求法。根据约数和定理:对于一个大于1正整数n可以[分解质因数][Link 1]：n=p1^a1\p2

曾经终败给现在/ 2022年05月28日 07:18/ 0 赞/ 216 阅读

相关 190507 | 约数个数

题目描述输入n个整数,依次输出每个数的约数的个数输入描述: > 输入的第一行为N，即数组的个数(N<=1000) 接下来的1行包括N个整数，其中每个数的范围为(1<

心已赠人/ 2022年02月04日 06:39/ 0 赞/ 215 阅读