bzoj1968: [Ahoi2005]COMMON 约数研究 ——by lethalboy

Day2                            

有约数个数定理： 

对于一个大于1正整数n可以分解质因数：

则n的正约数的个数就是

 

。

我们在筛素数表时记录最小因子，然后log分解质因数，用约数个数定理求约数个数。

总复杂度为O(nlogn)

然而，还有更简单的做法。。。。阮神讲的。。。。。

我们考虑对于某个数i，显然，i被作为约数计数了n/i次，那么总答案即为ans=∑(n/i)。

代码：

质因数分解法：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#define N 1000100
using namespace std;
typedef long long ll;
ll n,prime[N],cnt;
ll dy[N];bool is[N];
ll ans,s[N],t[N];
void init()
{for(ll i=2;i<=n;i++){if(!is[i]){prime[++cnt]=i;dy[i]=cnt;}for(ll j=1;j<=cnt;j++){ll tmp=prime[j]*i;if(tmp>N)break;is[tmp]=1;dy[tmp]=j;}}
}
ll solve(ll x)
{ll k=0,ret=1,la=-1;while(x!=1){if(la!=dy[x]){la=dy[x];ret=ret*(k+1);k=0;}k++;x/=prime[dy[x]];}ret=ret*(k+1);return ret;
}
int main()
{scanf("%lld",&n);init();for(ll i=1;i<=n;i++)t[i]=solve(i);for(ll i=1;i<=n;i++)ans+=t[i];printf("%lld\n",ans);
}

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<climits>
#include<cstring>
#include<algorithm>
using namespace std;
int n,ans;
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++)ans+=n/i;printf("%d\n",ans);
}