求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;
}
下一篇: 深度解析Nginx下的PHP框架路由实现