update:2017-04-16

当时写的比较naive，现在还是不要看了

 

【欧拉函数】

φ(n)=n(1-1/p1)(1-1/p2)...(1-1/pk)

通过上式易发现 p[j]|i时 phi[i*p[j]]=phi[i]*p[j] 因为phi[i]的n是n*p[j]/p[j]，其他的部分一样

[2017-01-02]

一种更感性的理解

就是说，phi[i]与phi[i*p[j]] 本来i有p[j]这个质因子，他们的差别就只有式子中开始的n了，只要乘上p[j]就可以了

没有p[j]的话，就是*(p[j]-1)/p[j]在处理n的差别*p[j]，最后就是p[j]-1；了

 

证明：http://www.cnblogs.com/candy99/p/6200660.html

void sieve(){    phi[1]=1;    for(int i=2;i<=n;i++){        if(!vis[i]){            p[++m]=i;            phi[i]=i-1;        }        for(int j=1;j<=m&&i*p[j]<=n;j++){            vis[i*p[j]]=1;            if(i%p[j]==0){                phi[i*p[j]]=phi[i]*p[j];                break;            }            phi[i*p[j]]=phi[i]*(p[j]-1);        }    }    for(int i=1;i<=n;i++) s[i]=s[i-1]+phi[i];}

---

【约数个数】

根据乘法原理，n的约数个数为∏{i=1...r}(ai+1)

由上式可得 p[j]|i时 facnum[i*p[j]]=facnum[i]/(minfac[i]+1)*(minfac[i*p[j]]+1)

 

---

 

【约数和】

n=p1^a1*p2^a2*…*pr^ar 

则其约数和=∏{i=1...r}(Σ{j=0..aj}pi^j) 就是考虑每个约数中的每个质因子选的指数

p[j]|i时，得到sumfac[i*p[j]]   (一下分析中a省去在那个数中)

需要除以Σ{i=1...a[minfac[i]]}p[j]^i

再乘以Σ{i=1...a[minfac[k]]}p[j]^i

其中a[minfac[k]]=a[minfac[i]]+1 

这样开两个辅助数组记录 

t1[i]=Σ{i=0...a[minfac[i]]}minfac[i]^i

t2[i]=mindiv[i]^a[minfac[i]]

int notp[N],p[N],mu[N],minfac[N],t1[N],t2[N],sf[N];

void sieve(){
        mu[1]=1;    sf[1].s=1;    for(int i=2;i

 还有一种方法，每个数i暴力更新倍数，时间也差不多