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

曾经终败给现在 2022-05-28 07:18 191阅读 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