欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-13 09:38:30
...

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

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

根据约数和定理:对于一个大于1正整数n可以分解质因数:n=p1^a1*p2^a2*p3^a3*…*pk^ak,则由约数个数定理可知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;
}