前64个自然数的表：

n	mu(n)	Smu(n)	phi(n)	Sphi(n)	d(n)	Sd(n)	sigma(n)	Ssigma(n)
1	1	1	1	1	1	1	1	1
2	-1	0	1	2	2	3	3	4
3	-1	-1	2	4	2	5	4	8
4	0	-1	2	6	3	8	7	15
5	-1	-2	4	10	2	10	6	21
6	1	-1	2	12	4	14	12	33
7	-1	-2	6	18	2	16	8	41
8	0	-2	4	22	4	20	15	56
9	0	-2	6	28	3	23	13	69
10	1	-1	4	32	4	27	18	87
11	-1	-2	10	42	2	29	12	99
12	0	-2	4	46	6	35	28	127
13	-1	-3	12	58	2	37	14	141
14	1	-2	6	64	4	41	24	165
15	1	-1	8	72	4	45	24	189
16	0	-1	8	80	5	50	31	220
17	-1	-2	16	96	2	52	18	238
18	0	-2	6	102	6	58	39	277
19	-1	-3	18	120	2	60	20	297
20	0	-3	8	128	6	66	42	339
21	1	-2	12	140	4	70	32	371
22	1	-1	10	150	4	74	36	407
23	-1	-2	22	172	2	76	24	431
24	0	-2	8	180	8	84	60	491
25	0	-2	20	200	3	87	31	522
26	1	-1	12	212	4	91	42	564
27	0	-1	18	230	4	95	40	604
28	0	-1	12	242	6	101	56	660
29	-1	-2	28	270	2	103	30	690
30	-1	-3	8	278	8	111	72	762
31	-1	-4	30	308	2	113	32	794
32	0	-4	16	324	6	119	63	857
33	1	-3	20	344	4	123	48	905
34	1	-2	16	360	4	127	54	959
35	1	-1	24	384	4	131	48	1007
36	0	-1	12	396	9	140	91	1098
37	-1	-2	36	432	2	142	38	1136
38	1	-1	18	450	4	146	60	1196
39	1	0	24	474	4	150	56	1252
40	0	0	16	490	8	158	90	1342
41	-1	-1	40	530	2	160	42	1384
42	-1	-2	12	542	8	168	96	1480
43	-1	-3	42	584	2	170	44	1524
44	0	-3	20	604	6	176	84	1608
45	0	-3	24	628	6	182	78	1686
46	1	-2	22	650	4	186	72	1758
47	-1	-3	46	696	2	188	48	1806
48	0	-3	16	712	10	198	124	1930
49	0	-3	42	754	3	201	57	1987
50	0	-3	20	774	6	207	93	2080
51	1	-2	32	806	4	211	72	2152
52	0	-2	24	830	6	217	98	2250
53	-1	-3	52	882	2	219	54	2304
54	0	-3	18	900	8	227	120	2424
55	1	-2	40	940	4	231	72	2496
56	0	-2	24	964	8	239	120	2616
57	1	-1	36	1000	4	243	80	2696
58	1	0	28	1028	4	247	90	2786
59	-1	-1	58	1086	2	249	60	2846
60	0	-1	16	1102	12	261	168	3014
61	-1	-2	60	1162	2	263	62	3076
62	1	-1	30	1192	4	267	96	3172
63	0	-1	36	1228	6	273	104	3276
64	0	-1	32	1260	7	280	127	3403

欧拉函数

不大于n的与n互质的数的个数。

对于n>2，欧拉函数都是偶数

单个欧拉函数：

inline int phi(int n) {    int res=n;    for(int i=1; i<=pritop&&pri[i]*pri[i]<=n; i++) {        if(n%pri[i]==0) {            res-=res/pri[i];            while(n%pri[i]==0)                n/=pri[i];        }        if(n==1)            return res;    }    if(n!=1)        res-=res/n;    return res;}

线性筛与杜教筛：

const int mod=1e9+7;const int MAXN=5e6;ll sphi[MAXN+1];int pri[MAXN+1];int &pritop=pri[0];void sieve(int n=MAXN) {    sphi[1]=1;    for(int i=2; i<=n; i++) {        if(!pri[i]) {            pri[++pritop]=i;            sphi[i]=i-1;        }        for(int j=1; j<=pritop; j++) {            int &p=pri[j];            int t=i*p;            if(t>n)                break;            pri[t]=1;            if(i%p) {                sphi[t]=sphi[i]*sphi[p];                if(sphi[t]>=mod)                    sphi[t]%=mod;            } else {                sphi[t]=sphi[i]*p;                if(sphi[t]>=mod)                    sphi[t]%=mod;                break;            }        }    }    for(int i=2; i<=n; i++) {        sphi[i]+=sphi[i-1];        if(sphi[i]>=mod)            sphi[i]%=mod;    }}unordered_map
    
      Sphi;inline ll Phi(ll n) {    if(n<=MAXN)        return sphi[n];    if(Sphi.count(n))        return Sphi[n];    ll ret=s1(n);    for(ll l=2,r; l<=n; l=r+1) {        ll t=n/l;        r=n/t;        ll tmp=r-(l-1);        tmp*=Phi(t);        if(tmp>=mod)            tmp%=mod;        ret-=tmp;        if(ret<0)            ret+=mod;    }    return Sphi[n]=ret;}
    

莫比乌斯函数

单个莫比乌斯函数：

inline int mu(int n){    int res=1;    for(int i=1; i<=pritop&&pri[i]*pri[i]<=n; i++) {        if(n%pri[i]==0) {            res=-res;            n/=pri[i];            if(n%pri[i]==0)                return 0;        }        if(n==1)            return res;    }    if(n!=1)        res=-res;    return res;}

线性筛与杜教筛：

const int MAXN=5e6;ll smu[MAXN+1];int pri[MAXN+1];int &pritop=pri[0];void sieve(int n=MAXN) {    smu[1]=1;    for(int i=2; i<=n; i++) {        if(!pri[i]) {            pri[++pritop]=i;            smu[i]=-1;        }        for(int j=1; j<=pritop; j++) {            int &p=pri[j];            int t=i*p;            if(t>n)                break;            pri[t]=1;            if(i%p) {                smu[t]=-smu[i];            } else {                smu[t]=0;                break;            }        }    }    for(int i=2; i<=n; i++) {        smu[i]+=smu[i-1];    }}unordered_map
    
      Smu;inline ll Mu(ll n) {    if(n<=MAXN)        return smu[n];    if(Smu.count(n))        return Smu[n];    ll ret=1;    for(ll l=2,r; l<=n; l=r+1) {        ll t=n/l;        r=n/t;        ll tmp=r-(l-1);        tmp*=Mu(t);        ret-=tmp;    }    return Smu[n]=ret;}
    

因数个数函数\(d(n)\)

线性筛：

前缀和：

一次分块就可以求出来，比杜教筛还快，要什么杜教筛？

ll d(int n){    ll ret=0;    for(int l=1,r;l<=n;l=r+1){        r=n/(n/l);        ret+=(r-l+1)*(n/l);    }    return ret;}

除数函数\(\sigma _{x}(n)\)

积性。

n的所有因子的x次方和。

\(\sigma _{0}(n)\) 0阶的除数函数就是 \(d(n)\)

---

其他遇到过的奇怪组合

\(id(n)*d(n)\)

积性，但是有比杜教筛更快的办法：

只讨论前缀和，类似\(d(n)\)，每次贡献的式子带个公差罢了。

int sum(int a1,int an,int n){    return (a1+an)*n/2;}ll id_d(int n){    ll ret=0;    for(int l=1,r;l<=n;l=r+1){        r=n/(n/l);        ret+=sum(1,n/l,n/l)*sum(l,r,r-l+1);    }    return ret;}

\(id(n)*\varphi(n)\)

显然积性，可以用杜教筛。

卷一个 \(id\) 用杜教筛，一般有几个 \(id\) 就卷几个 \(id\) 。

记\(f(n)=id(n)*\varphi(n)\)

记\(S(n)=\sum\limits_{i=1}^{n} f(i)\)

要求的就是\(S(n)\)

假如我们找到一个\(g\)，使得\((f*g)(n)\)（\(f\)与\(g\)的狄利克雷卷积）的前缀和很好求，且\(g(n)\)也很好求，那么可以用杜教筛。

显然：

\((f*g)(n)=\sum\limits_{d|n} f(d)g(\frac{n}{d})=\sum\limits_{d|n} d\varphi(d)g(\frac{n}{d})\)

若令\(g(n)=n\)，即\(g=id\)，有：

\((f*g)(n)=n\sum\limits_{d|n} \varphi(d)\)

后面那个：

\(\sum\limits_{d|n} \varphi(d)=n\)

所以：

\((f*g)(n)=n^2\)

由杜教筛公式：

\(g(1)S(n)=\sum\limits_{i=1}^{n}(f*g)(i) - \sum \limits _{i=2}^{n} g(i) S(\lfloor \frac{n}{i} \rfloor)\)

由于某些特殊的原因，好像\(g(1)\)总是\(1\)，代进去可以得到：

\(S(n)=\sum\limits_{i=1}^{n}i^2 - \sum \limits _{i=2}^{n} i S(\lfloor \frac{n}{i} \rfloor)\)

后面那个套一个分块就可以了。

---

可能会常用的公式：

\(s_1(n)=\sum\limits_{i=1}^{n}i=\frac{1}{2}n(n+1)\)

\(s_2(n)=\sum\limits_{i=1}^{n}i^2=\frac{1}{6}n(n+1)(2n+1)\)

\(s_3(n)=\sum\limits_{i=1}^{n}i^3=\frac{1}{4}n^2(n+1)^2\)