参考博客 参考博客 参考博客 预备知识点： 大于1的数n可以分解质因数： n=p1a1×p2a2×p3a3*…*pka n的约数的个数是(a1+1) * (a2+1) * (a3+1)…(ak+1) 我们先用线性筛来筛出素数
bool mark[maxn]; int prim[maxn]; int cnt; void initial() { cnt=0; for (int i=2 ; i<N ; ++i) { if (!mark[i]) prim[cnt++]=i;//存放素数 for (int j=0 ; j<cnt && i*prim[j]<N ; ++j) { mark[i*prim[j]]=1;//标记为素数 if (!(i%prim[j])) break; } } }n的约数的个数是(a1+1) * (a2+1) * (a3+1)…(ak+1) 我们可以用线性筛筛出当前n的约数个数 证明： d[i]表示i的约数的个数 num[i]表示i的最小素因子的个数 prim[i]表示第i个素数 分下列情况：
i为质数 因为i为质数，所以素因子只有本身，且指数为1 所以num[i]=1,d[i]=2(1和本身)i%prim[j]!=0 说明i不包含prim[j]这个素因子，但是i*prim[j]包含一个素因子prim[j]，所以 d(i∗prime[j])=(1+r1)∗……∗(1+rk)∗(1+1)=d[i] * d[prim[j]] = d[i] * 2 而且因为我们是从小到大枚举，所以当前的prim[j]必然是i * prim[j]的最小素因子，所以num[i * prim[j]] = 1i%prim[j]= =0 i中包含prim[j]，且为i的最小素因子 d(i∗prime[j])=(1+r1+1)∗……∗(1+rk) d(i∗prime[j])=d(i)/(num(i)+1)∗(num(i)+2) num(i∗prime[j])=num(i)+1 #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int wx=1017; int isprime[wx],prime[wx],d[wx],num[wx]; int tot,n,m; inline int read(){ int sum=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();} return sum*f; } void Euler(){ memset(isprime,1,sizeof isprime); d[1]=1; for(int i=2;i<=n;i++){ if(isprime[i]){ prime[++tot]=i; d[i]=2; num[i]=1; } for(int j=1;j<=tot&&i*prime[j]<=n;j++){ isprime[i*prime[j]]=0; if(i%prime[j]==0){ d[i*prime[j]]=d[i]/(num[i]+1)*(num[i]+2); num[i*prime[j]]=num[i]+1; break; } else{ d[i*prime[j]]=d[i]*d[prime[j]]; num[i*prime[j]]=1; } } } } int main(){ n=read(); Euler(); for(int i=1;i<=n;i++)printf("%d %d\n",i,d[i]); return 0; }我们用sd(i)表示i的约数和 根据算数基本定理： sd(n)=(1+p1+p21+……+pr11)∗(1+p2+p22+……+pr22)∗……∗(1+pk+p2k+……+prkk) 最小质因子的那一项是(1+p1+p21+……+pr11) 我们用num[i]来表示最小质因子的那一项 证明： 和上面一样分类讨论：
i为素数 sd(i)=i+1num(i)=i+1i%prim[j] ! = 0 i∗prime[j]里原先没有prime[j]这一项，加上后： sd(i∗prime[j])=sd(i)∗sd(prime[j]) num(i∗prime[j])=1+prime[j] （大体思路如上）i%prim[j] = =0 d(i∗prime[j])=(d(i)/num(i)∗(num(i)∗prime[j])+1 num(i∗prime[j])=num(i)∗prime[j]+1