莫比乌斯反演的前置知识：https://www.cnblogs.com/yyc-jack-0920/p/10556351.html
杜教筛可以在$O(n^{2/3})$的时间内求出积性函数的前缀和即$\sum\limits_{i=1}^n f(i)$
实现过程需要找到另一个积性函数$g$使得$f*g$为一个方便计算的函数
$\sum f*g=\sum\limits_{i=1}^n \sum\limits_{d|i} g(d)f(i/d) $
$=\sum\limits_{d=1}^n g(d) \sum\limits_{t=1}^{n/d} f(t)$
$=g(1)\sum\limits_{i=1}^n f(i) + \sum\limits_{d=2}^n g(d) \sum\limits_{i=1}^{n/d} f(i)$
设前缀和为$S(i)$ 即$g(1)S(n)=-\sum\limits_{d=2}^n g(d) S(n/d)+\sum f*g$
这样就写成了一个数论分块的递归形式，复杂度可以证明（
同时，由于杜教筛自带数论分块形式，因此在外面再套一层数论分块并不会影响复杂度
luogu 4213 【模板】杜教筛：
求$\phi$与$\mu$的前缀和
有结论：$\phi*1=id$、$\mu *1 =[n=1]$ 直接套用公式即可
1 #include<bits/stdc++.h>
2 #define inf 2139062143
3 #define MAXN 5001001
4 #define MOD 1000000007
5 #define ll long long
6 #define ull unsigned long long
7 #define rep(i,s,t) for(register int i=(s),i##end=(t);i<=i##end;++i)
8 #define dwn(i,s,t) for(register int i=(s),i##end=(t);i>=i##end;--i)
9 #define ren for(register int i=fst[x];i;i=nxt[i])
10 #define Fill(a,b) memset(a,b,sizeof(a))
11 #define pls(a,b) ((a+b)%MOD+MOD)%MOD
12 #define mns(a,b) (((a)-(b))%MOD+MOD)%MOD
13 #define mul(a,b) (1LL*(a)*(b)%MOD)
14 #define pii pair<int,int>
15 #define mp(a,b) make_pair(a,b)
16 #define pb(i,x) vec[i].push_back(x)
17 #define fi first
18 #define se second
19 using namespace std;
20 inline ll read()
21 {
22 ll x=0;bool f=1;char ch=getchar();
23 while(!isdigit(ch)) {if(ch=='-') f=0;ch=getchar();}
24 while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
25 return f?x:-x;
26 }
27 int lmt,ntp[MAXN],p[MAXN],tot;ll mu[MAXN],phi[MAXN];
28 void mem(int n)
29 {
30 mu[1]=phi[1]=1;rep(i,2,n)
31 {
32 if(!ntp[i]) p[++tot]=i,mu[i]=-1,phi[i]=i-1;
33 rep(j,1,tot) if(1LL*i*p[j]>n) break;
34 else
35 {
36 ntp[i*p[j]]=1;if(i%p[j]) mu[i*p[j]]=-mu[i],phi[i*p[j]]=phi[i]*phi[p[j]];
37 else {phi[i*p[j]]=phi[i]*p[j];break;}
38 }
39 }
40 rep(i,1,n) mu[i]+=mu[i-1],phi[i]+=phi[i-1];
41 }
42 unordered_map<int,ll> ansm,ansp;
43 ll smu(ll n,ll res=0)
44 {
45 if(n<=lmt) return mu[n];if(ansm[n]) return ansm[n];
46 for(ll l=2,r;l<=n;l=r+1) r=n/(n/l),res+=smu(n/l)*(r-l+1);
47 return ansm[n]=1LL-res;
48 }
49 ll sphi(ll n,ll res=0)
50 {
51 if(n<=lmt) return phi[n];if(ansp[n]) return ansp[n];
52 for(ll l=2,r;l<=n;l=r+1) r=n/(n/l),res+=sphi(n/l)*(r-l+1);
53 return ansp[n]=1LL*n*(n+1)/2-res;
54 }
55 int main()
56 {
57 int T=read(),n;mem(lmt=5000000);
58 while(T--) {n=read();printf("%lld %lld\n",sphi(n),smu(n));}
59 }
View Code
51nod 1237 最大公约数之和V3
题目大意：
求$\sum\limits_{i=1}^n \sum\limits_{j=1}^{n} gcd(i,j)$
思路：
原式=$\sum\limits_{d=1}^{n} d \sum\limits_{i=1}^{n/d} \sum\limits_{j=1}^{n/d} [gcd(i,j)==1]$
$\sum\limits_{d=1}^n d \sum\limits_{i=1}^{n/d} \mu(i) \lfloor\frac{n}{id}\rfloor \lfloor\frac{n}{id}\rfloor$
$\sum\limits_{g=1}^n \lfloor\frac{n}{g}\rfloor \lfloor\frac{n}{g}\rfloor \sum\limits_{d|g} \mu(d)*\frac{g}{d}$
$\sum\limits_{g=1}^n \lfloor\frac{n}{g}\rfloor \lfloor\frac{n}{g}\rfloor \cdot \phi(g)$
数论分块+杜教筛求欧拉函数前缀和即可
1 #include<bits/stdc++.h>
2 #define inf 2139062143
3 #define MAXN 5001001
4 #define MOD 1000000007
5 #define ll long long
6 #define ull unsigned long long
7 #define rep(i,s,t) for(register int i=(s),i##end=(t);i<=i##end;++i)
8 #define dwn(i,s,t) for(register int i=(s),i##end=(t);i>=i##end;--i)
9 #define ren for(register int i=fst[x];i;i=nxt[i])
10 #define Fill(a,b) memset(a,b,sizeof(a))
11 #define pls(a,b) (a+b)%MOD
12 #define mns(a,b) (a-(b)+MOD)%MOD
13 #define mul(a,b) (1LL*(a)*(b)%MOD)
14 #define pii pair<int,int>
15 #define mp(a,b) make_pair(a,b)
16 #define pb(i,x) vec[i].push_back(x)
17 #define fi first
18 #define se second
19 using namespace std;
20 inline ll read()
21 {
22 ll x=0;bool f=1;char ch=getchar();
23 while(!isdigit(ch)) {if(ch=='-') f=0;ch=getchar();}
24 while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
25 return f?x:-x;
26 }
27 int ntp[MAXN],p[MAXN],tot;ll phi[MAXN],lmt,n;
28 const int inv2=500000004;
29 void mem(int n)
30 {
31 phi[1]=1;rep(i,2,n)
32 {
33 if(!ntp[i]) p[++tot]=i,phi[i]=i-1;
34 rep(j,1,tot) if(1LL*i*p[j]>n) break;
35 else
36 {
37 ntp[i*p[j]]=1;if(i%p[j]) phi[i*p[j]]=mul(phi[i],phi[p[j]]);
38 else {phi[i*p[j]]=mul(phi[i],p[j]);break;}
39 }
40 }
41 rep(i,1,n) phi[i]=pls(phi[i-1],phi[i]);
42 }
43 map<ll,int> ansp;
44 ll sum(ll n)
45 {
46 n%=MOD;return mul(mul(n,n+1),inv2);
47 }
48 ll sphi(ll n,ll res=0)
49 {
50 if(n<=lmt) return phi[n];if(ansp[n]) return ansp[n];
51 for(ll l=2,r;l<=n;l=r+1) r=n/(n/l),res=pls(mul(sphi(n/l),(r-l+1)%MOD),res);
52 return ansp[n]=mns(sum(n),res);
53 }
54 ll solve(ll n,ll res=0)
55 {
56 for(ll l=1,r;l<=n;l=r+1)
57 r=n/(n/l),res=pls(res,mul(mul((n/l)%MOD,(n/l)%MOD),mns(sphi(r),sphi(l-1))));
58 return res;
59 }
60 int main()
61 {
62 n=read();mem(lmt=5000000);printf("%lld\n",solve(n));
63 }
View Code
51nod 1238 最大公倍数之和V3
题目大意：
求$\sum\limits_{i=1}^n \sum\limits_{j=1}^{n} lcm(i,j)$
思路：
原式=$\sum\limits_ {i=1}^n \sum\limits_{j=1}^{n} \frac{ij}{gcd(i,j)}$
$\sum\limits_{d=1}^n \ \frac{1}{d}\ \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} i \cdot j [gcd(i,j)==d]$
$\sum\limits_{d=1}^n \ d\ \sum\limits_{i=1}^{n/d} \sum\limits_{j=1}^{n/d} i \cdot j [gcd(i,j)==1]$
$\sum\limits_{d=1}^n \ d \ \sum\limits_{g=1}^{n/d} \mu(g) \sum\limits_{i=1}^{n/d} i\cdot[g|i] \sum\limits_{j=1}^{n/d} j \cdot [g|j]$
$\sum\limits_{d=1}^n \ d\ \sum\limits_{g=1}^{n/d} \mu(g) g^2 \sum\limits_{i=1}^{n/gd} i \sum\limits_{j=1}^{n/gd} j$
$\sum\limits_{g=1}^n \lgroup \frac{1}{2} \lfloor \frac{n}{g} \rfloor \cdot \lgroup \lfloor \frac{n}{g} \rfloor +1\rgroup\rgroup^2 \sum\limits_{d|g} \mu(g) g^2 \frac{d}{g}$
记：$f(i)=\sum\limits_{d|i} \mu(i) i^2 \frac{d}{i}$即$f(i)=(\mu \cdot id^2) * id$ 、记前缀和$S(i)=\frac{i(i+1)}{2}$
原式=$\frac{1}{2} \sum\limits_{g=1}^{n} S(\lfloor \frac{n}{g}\rfloor)^2 f(g) \ \ \ \ \ \ \textbf{\lbrack1\rbrack}$
在这种形式下，只需考虑求$f(i)$前缀和，不妨令$g(i)=id^2$，则有：
$f*g=((\mu \cdot id^2)*id)*id^2$
由于$dirichlet$卷积满足交换律：
$f*g=((\mu\cdot id^2)*id^2)*$id$
$(f*g)(n)=\sum\limits_{g|n} (\sum\limits_{d|g} \mu(d)\cdot d^2\cdot \frac{g^2}{d^2})\cdot \frac{n}{g}$
$=\sum\limits_{g|n} g^2\cdot [g=1] \cdot \frac{n}{g}$
$=n \sum\limits_{g|n} g\cdot [g=1]$
$=n$
记$s(n)=\sum\limits_{i=1}^n f(i)$
代入杜教筛公式即有$s(n)=-\sum\limits_{i=2}^n g(i) s(n/i) +\sum\limits_{i=1}^n i$
利用平方和公式求$g(i)$的区间和即可用杜教筛求出$f(i)$的前缀和
再套用式$\textbf{\lbrack 1 \rbrack}$求和即可
1 #include<bits/stdc++.h>
2 #define ll long long
3 #define MAXN 5001001
4 #define inf 2139062143
5 #define MOD 1000000007
6 #define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
7 #define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
8 #define ren for(int i=fst[x];i;i=nxt[i])
9 #define pls(a,b) (a+b)%MOD
10 #define mns(a,b) (a-(b)+MOD)%MOD
11 #define mul(a,b) (1LL*(a)*(b))%MOD
12 using namespace std;
13 int isp[MAXN],p[MAXN],tot;ll f[MAXN],s[MAXN],lmt,n;
14 const int inv2=500000004,inv6=166666668;
15 void mem(int n)
16 {
17 f[1]=1;rep(i,2,n)
18 {
19 if(!isp[i]) p[++tot]=i,f[i]=1-i;
20 rep(j,1,tot) if(1LL*i*p[j]>n) break;
21 else {isp[i*p[j]]=1;if(i%p[j]) f[i*p[j]]=f[i]*f[p[j]];else {f[i*p[j]]=f[i];break;}}
22 }
23 rep(i,1,n) f[i]=pls(f[i-1],mul(f[i],i));
24 }
25 map<ll,int> ansf;
26 inline ll sum(ll n)
27 {
28 n%=MOD;return mul(mul(n,n+1),mul(2*n+1,inv6));
29 }
30 inline ll gets(ll n)
31 {
32 n%=MOD;return mul(mul(n,n+1),inv2);
33 }
34 ll sumf(ll n,ll res=0)
35 {
36 if(n<=lmt) return f[n];if(ansf[n]) return ansf[n];
37 for(ll l=2,r;l<=n;l=r+1) r=n/(n/l),res=pls(res,mul(mns(sum(r),sum(l-1)),sumf(n/l)));
38 return ansf[n]=mns(gets(n),res);
39 }
40 ll solve(ll n,ll res=0)
41 {
42 for(ll l=1,r;l<=n;l=r+1)
43 r=n/(n/l),res=pls(res,mul(mul(gets(n/l),gets(n/l)),mns(sumf(r),sumf(l-1))));
44 return (res+MOD)%MOD;
45 }
46 int main()
47 {
48 scanf("%lld",&n);mem(lmt=5000000);printf("%lld\n",solve(n));
49 }
View Code
51nod