约数个数统计问题探究
衡阳市第八中学 邹毅
约数个数统计问题是在算法学习过程 一个非常经典的问题，一般的描述为给出一个正整数N，请求出它的所有约数的个数，例如当N为6的时候，它的约数为1，2，3，6共4个。当N的范围不断变化，并且询问范围从单个数到某个区间进行变化时，解法趋于多样化，本文尝试进行一些归纳总结。
例题1:询问某个数字N的约数个数，N<= 1e6
解法:可从约数的定义出发，进行暴力求解即可，时间复杂度为O(N)
代码如下:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
int sum=0;
cin>>n;
for (int i=1;i<=n;i++)
if (n%i==0)
sum++;
cout<<sum<<endl;
}
例题2:询问某个数字N的约数个数，N<= 1e9.
解法:发现N的约数总是成对成对的出现，例如当N=12时，可分解成如下形式:
N=12=1*12=2*6=3*4
可将这些分解形式统一写成N=a*b，a<=b.于是只需要枚举a的范围，判断a是否为N的约数，如果满足条件的话，还可以同时得到另一个约数b=N/a.需要注意的是如果a=b的话，则只能被统计1次. 时间复杂度为O(sqrt(N))
代码如下:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
int sum=0;
cin>>n;
for (int i=1;i*i<=n;i++)
{
if (n%i==0)
sum=sum+2;
if (i*i==n)
sum--;
}
cout<<sum<<endl;
}
一般来说，统计数字N的约数个数用上面这个算法即可，如果希望常数更小一点的话，可以利用数论知识进行优化,其对10^18之内的随机数据的表现还是很不错的。
方法如下:
1:利用惟一分解定理，对数字N进行质因子分解,例如12可分解成2^2*3^1。
2:使用乘法原理，如果数字x为12的约数，则x也必然可分解成2^a*3^b的形式，并且0<=a<=2,0<=b<=1，即a有3种选择，b有2种选择,x共有6种选择。
代码如下:
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n,i,j,m,sum,ans=1;
cin>>n;
for(i=2; i*i<=n; i++)
{
sum=0;
while(n%i==0)
{
n/=i;
sum++;
}
ans*=(sum+1);
}
if(n!=1)ans*=2;
cout<<ans<<endl;
return 0;
}
接下来我们尝试求解某个范围的所有数字的约数的总和。
例题3：
对于输入一个数字，输出其约数个数。例如10就有4个约数1,2,5,10 。这种问题，小可可已做得非常熟练了。现在老师将这个问题变了下：给出一个数字N，求1到N之间每个数字的约数个数，再输出其累加和
Input
一个数字N
N< =1e6
Output
如题
输入数据 1
3
输出数据 1
5
题解:可枚举数字N，如果套用前面例题2中的常规做法的法，将超时两个点，但使用例题2的优化算法的话，将顺利Ac.
用时2396ms,时间复杂度为O(2/3*N*sqrt(N))
代码如下:
#include<bits/stdc++.h>
using namespace std;
int dfs(int n)
{
int sum=1;
for(int i=2;i<=sqrt(n);i++)
{
int cnt=0;
while(n%i==0)
{
cnt++;
n/=i;
}
sum*=(cnt+1);
}
if(n>1) sum*=2;
return sum;
}
int main()
{
int n,ans=0;
cin>>n;
for(int i=1;i<=n;i++)
ans+=dfs(i);
cout<<ans<<endl;
return 0;
}
优化方法1:使用欧拉筛法进行状态之间的转移，用时1987ms,一般认为欧拉筛法的时间复杂度为O(N)的，但也有人认为是O(N*log2N)的。
代码如下:
#include <iostream>
using namespace std;
const int n = 1e7;
const int N = n + 1;
int m=0;
int a[N], b[N], c[N], d[N];
int f[N], g[N];
void init()
{
f[1] = g[1] = 1;
for (int i = 2; i <= n; i++)
{
if (!a[i])
{
b[++m] = i;
c[i] = 1, f[i] = 2;
}
for (int j = 1; j <=m && b[j] * i <= n; j++)
{
int k = b[j];
a[i * k] = 1;
if (i % k == 0)
{
c[i * k] = c[i] + 1;
f[i * k] = (f[i] / (c[i]+1))* (c[i * k] + 1);
break;
}
else
{
c[i * k] = 1;
f[i * k] = 2 * f[i];
}
}
}
}
int main()
{
init();
int x;
cin>>x;
int ans=0;
for (int i=1;i<=x;i++)
ans=ans+f[i];
cout<<ans<<endl;
return 0;
}
优化方法2:使用数论分段方法进行求解。
方法如下:枚举数字i做为约数，统计其在[1..N]有多少个倍数即N/i,然后将出现次数一样的约数进行合并统计，例如
当N=20，i=7时，易知7在1到20之间有2个倍数，分别为7，14，于是在统计7与14的约数时，i就将做出贡献。
同理当i=8,9,10时，它们也是出现2次的，于是可以进行合并统计，使用数学分析可知这样的分段个数至多为2*sqrt(N)个，于是时间复杂度为O(sqrt(N))，对于本题用时11ms,易可可轻松应对1e14这样的数据范围。
代码如下
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
int main()
{
ll n;
scanf("%lld",&n);
ll res = 0;
for(int i=1;i<=n;) {
int r = n/(n/i)+1;
res += (n/i) * (r - i);
i = r;
}
printf("%lld\n",res);
return 0;
}
优化方法3:使用容斥定理
方法如下:对于数字N，其可分解成N=i*j的形式，为了不重复统计，一般要求i<=j。于是可以枚举i,算出其出现次数并进行累加，最后将累加结果乘以2，得到一个结果。这个结果是没有考虑i与j的大小关系的，于是要从其中减去i>j的情况，并且将i=j的情况只能统计1次，统计分析可知要减去的值正好为int(sqrt(n))* int(sqrt(n))。时间复杂度为O(sqrt(N)),但胜在代码清爽至极，最终感悟是OI的尽头是数学。
代码如下:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,sum=0;
cin>>n;
int nn=sqrt(n);
for(int i=1;i<=n/i;i++)
sum=sum+n/i;
cout<<sum*2-nn*nn<<endl;
return 0;
}
标签：约数,int,sum,个数,探究,using,include From： https://www.cnblogs.com/oiteacher/p/17158487.html