Divisor counting
题目大意：定义f(n)表示整数n的约数个数。给出正整数n，求f(1)+f(2)+...+f(n)的值。
注释：1<=n<=1000,000
想法：我们再次有两种做法：文...武.....。想讲武的......我们其实这次更博只是为了介绍一种知识点——线性筛法筛积性函数。这里，给出线性筛的万能筛法。
1.初值：显然，初值是必要的。
2.我们类比欧拉筛，用k(n)举例。当n是素数时的情况使我们必须的，这相当于初值一样重要。
3.又因为，我们主要筛积性函数，显然函数是否为积性。如果gcd(a,b)=1，我们需要知道k(a*b)是否等于k(a)*f(b)。
4.紧接着，我们需要知道如果n是整数的幂次，有什么用呢？在5中我们会用到。
5.最后的，我们需要明白对于任意的a来讲，如果这个a被prime[j]筛到了，我们思考如何才能将k(a)用我们已知的值筛出。我们讨论：
1)如果gcd(prime[i],a)=prime[j]，我们设想：我们可以记录a的最小质因子以及这个最小质因子的个数，显然：a的最小质因子一定是prime[j]。为什么？因为线性筛保证每一个数是会被它的最小质因子筛掉。prime[j]*a的最小质因子如果不是prime[j]，那它为什么会被prime[j]筛到？不会啊！它只会被最小者筛掉，所以我们此时保证了a的最小质因子一定不小于prime[j]。又因为此时我们发现：prime[j] | a 所以，我们知道，a的最小质因子一定是prime[j]。我们又记录了a中最小质因子的幂次h(a)，所以现在，我们就得出了$a\cdot prime[j]=\frac{a}{pirme[j]^{h(a)}}\cdot {prime[j]^{h(a)+1}}$。这时，我们用到了第3条，$\frac{a}{prime[j]^{h(i)}}$和$prime[j]^{h(i)+1}$显然是互质的！$\frac{a}{prime[j]^{h(i)}}$的值我们显然已经求过，$prime[j]^{h(i)+1}$的值呢？第4条在这里！所以这种情况就证好了。
2)如果gcd(prime[i],a)!=prime[j]，那么我们想，它会等于什么？我们已经证明了g(i)是一定不小于prime[j]，此时，g(i)！=prime[j]。所以，显然的，我们有g(i)>prime[j]。但是！此时我们有知道g(i)是i的最小质因子....质因子！！！由于此函数是积性函数，所以，$f(i\cdot prime[j])=f(i)\cdot f(prime[j])$。这...用第2点，证毕。
文的做法我们会带数论の一波流里提到（数论の一波流的[二]？猛戳），在此不讲......
最后，附上丑陋的代码......
#include <iostream>
#include <cstdio>
#include <cstring>
typedef long long ll;
using namespace std;
int prime[];
int h[];//h(i)表示i的最小质因子的个数，即g(i)^h(i)|i但g(i)^(h(i)+1)不行。
int g[];//g(i)表示i的最小质因子
int gh[];
bool v[]={false};
int sigema[];
int cnt=;
int quick_power(int a,int b)
{
int ans=;
while(b)
{
if(b&) ans=(ans*a);
b>>=;
a=(a*a);
}
return ans;
}
int main()
{
cnt=;
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)//我们先快筛g和h，其余的再说.
{
if(!v[i]) prime[++cnt]=i,g[i]=i,h[i]=,gh[i]=i;
for(int j=;i*prime[j]<=n&&j<=cnt;j++)
{
v[i*prime[j]]=;
g[i*prime[j]]=prime[j];
if(g[i]==prime[j])
{
h[i*prime[j]]=h[i]+;
gh[i*prime[j]]=quick_power(g[i*prime[j]],h[i*prime[j]]);
break;
}
else h[i*prime[j]]=,gh[i*prime[j]]=prime[j];
}
}
/*for(int i=1;i<=cnt;i++)
{
printf("Prime%d:%d\n",i,prime[i]);
}
for(int i=1;i<=n;i++)
{
printf("%d:%d^%d=%d\n",i,g[i],h[i],gh[i]);
}*/
memset(v,,sizeof(v));
cnt=;
sigema[]=;
for(int i=;i<=n;i++)
{
if(!v[i]) cnt++,sigema[i]=;
for(int j=;i*prime[j]<=n&&j<=cnt;j++)
{
v[i*prime[j]]=;
if(g[i]==prime[j]){sigema[i*prime[j]]=sigema[i/gh[i]]*(h[i]+);break;}
else sigema[i*prime[j]]=sigema[i]*;
}
}
/*for(int i=1;i<=n;i++)
{
printf("Sigema[%d]=%d\n",i,sigema[i]);
}*/
ll ans=;
for(int i=;i<=n;i++)
{
ans+=sigema[i];
}
printf("%lld",ans);
return ;
}
小结：错误，太多了....看看吧......