#include<bits/stdc++.h> using namespace std; /* 数论函数表 i phi(i) PHI(i) muu(i) MUU(i) ddd(i) DDD(i) sig(i) SIG(i) 1 1 1 1 1 1 1 1 1 2 1 2 -1 0 2 3 3 4 3 2 4 -1 -1 2 5 4 8 4 2 6 0 -1 3 8 7 15 5 4 10 -1 -2 2 10 6 21 6 2 12 1 -1 4 14 12 33 7 6 18 -1 -2 2 16 8 41 8 4 22 0 -2 4 20 15 56 9 6 28 0 -2 3 23 13 69 10 4 32 1 -1 4 27 18 87 11 10 42 -1 -2 2 29 12 99 12 4 46 0 -2 6 35 28 127 13 12 58 -1 -3 2 37 14 141 14 6 64 1 -2 4 41 24 165 15 8 72 1 -1 4 45 24 189 16 8 80 0 -1 5 50 31 220 17 16 96 -1 -2 2 52 18 238 18 6 102 0 -2 6 58 39 277 19 18 120 -1 -3 2 60 20 297 20 8 128 0 -3 6 66 42 339 21 12 140 1 -2 4 70 32 371 22 10 150 1 -1 4 74 36 407 23 22 172 -1 -2 2 76 24 431 24 8 180 0 -2 8 84 60 491 25 20 200 0 -2 3 87 31 522 26 12 212 1 -1 4 91 42 564 27 18 230 0 -1 4 95 40 604 28 12 242 0 -1 6 101 56 660 29 28 270 -1 -2 2 103 30 690 30 8 278 -1 -3 8 111 72 762*/ /**** * 超级积性函数线性筛 * ****/ typedef long long ll; const ll maxn=5e6; ll no_pri[maxn]={0,1,0},pri[maxn],low[maxn]; ll PHI[maxn],DDD[maxn],XDX[maxn],MUU[maxn],SIG[maxn]; void f_ini(){ for(ll i=2;i<maxn;i++){ if(!no_pri[i]) low[i]=pri[++pri[0]]=i; for(ll j=1;pri[j]*i<maxn;j++){ no_pri[pri[j]*i]=1; if(i%pri[j]==0) { low[pri[j]*i]=low[i]*pri[j]; break; } else low[pri[j]*i]=pri[j]; } } DDD[1]=PHI[1]=MUU[1]=SIG[1]=1;// 改这里 for(ll i=1;i<=pri[0];i++){ for(ll mul=pri[i],ct=1;mul<maxn;mul*=pri[i],ct++){ DDD[mul]=ct+1;// 改这里 SIG[mul]=SIG[mul/pri[i]]+mul;// 改这里 MUU[mul]=ct==1?-1:0;// 改这里 PHI[mul]=mul/pri[i]*(pri[i]-1);// 改这里 } } for(ll i=2;i<maxn;i++){ for(ll j=1;pri[j]*i<maxn;j++){ ll x=low[i*pri[j]], y=i*pri[j]/x; DDD[x*y]=DDD[x]*DDD[y]; MUU[x*y]=MUU[x]*MUU[y]; PHI[x*y]=PHI[x]*PHI[y]; SIG[x*y]=SIG[x]*SIG[y]; if(i%pri[j]==0) break; } } for(ll i=1;i<maxn;i++) { DDD[i]+=DDD[i-1]; MUU[i]+=MUU[i-1]; PHI[i]+=PHI[i-1]; SIG[i]+=SIG[i-1]; XDX[i]=(DDD[i]-DDD[i-1])*i+XDX[i-1]; } } int main(){ f_ini(); printf("数论函数表\n"); printf(" i phi(i) PHI(i) muu(i) MUU(i) ddd(i) DDD(i) sig(i) SIG(i)\n"); for(ll i=1;i<=30;i++) { printf("%2lld %3lld %6lld %6lld %6lld %6lld %6lld %6lld %6lld\n",i,PHI[i]-PHI[i-1],PHI[i],MUU[i]-MUU[i-1],MUU[i],DDD[i]-DDD[i-1],DDD[i],SIG[i]-SIG[i-1],SIG[i]); } return 0; }