前置知识
数论分块
P2261 [CQOI2007] 余数求和
:::info[代码]
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,l,r,k,ans;
signed main()
{cin>>n>>k;while(1){l=r+1;r=k/(k/l);if(r>k)r=k;if(r>n)r=n;ans+=(l+r)*(k/l)*(r-l+1)/2;if(r==k)break;if(r==n)break;}ans=n*k-ans;cout<<ans;return 0;
}
:::
积性函数
定义&性质
\[f(x\cdot y)=f(x)\cdot f(y) (\gcd(x,y)=1)
\]
常见积性函数
\[1,\varphi,\mu,\varepsilon,id_k,d,\sigma...
\]
解释：
\[1(x)=1
\]
\[\varphi(x)=\sum^x_{i=1}[\gcd(i,x)=1]
\]
\[\mu(x)=\begin{cases}1 \qquad n=1\\0 \qquad n含有平方因子\\(-1)^k\qquad k为n的质因子个数
\end{cases}\]
\[\varepsilon(x)=\begin{cases}1\qquad x=1\\0\qquad x\neq1
\end{cases}\]
\[id_k(x)=x^k
\]
\[\sigma_k(x)=\sum_{d|x}d^k
\]
\[d(x)=\sigma_0(x)
\]
莫比乌斯函数
线性筛求法
:::info[代码]
mu[1]=1;for(int i=2;i<=n;i++){if(!book[i]){prime[++pnum]=i;mu[i]=-1;}for(int j=1;j<=pnum&&i*prime[j]<=n;j++){book[i*prime[j]]=1;if(i%prime[j]==0){mu[i*prime[j]]=0;break;}mu[i*prime[j]]=-mu[i];}}
:::
狄利克雷卷积
定义
若函数 \(f,g,h\) 满足：
\[f(n)=\sum_{d|n}g(d)h(\frac{n}{d})
\]
则称 \(f\) 为 \(g,h\) 的狄利克雷卷积，记作 \(f=g*h\)
举例
\[f*1=\sum_{d|n}f(d)
\]
\[f*\varepsilon=f
\]
\[1*\mu=\varepsilon
\]
莫比乌斯反演核心函数
\[\varphi*1=id
\]
\[id*\mu=\varphi
\]
\[\sigma_k*\mu=id_k
\]
\[\mu*1=\varepsilon
\]
反演
公式一：GCD的处理
:::info[公式]
\[\begin{aligned}
[\gcd(i,j)=1]&=\varepsilon(\gcd(i,j))\\
&=\sum_{k|i且k|j}\mu(k)
\end{aligned}\]
:::
公式二：整除 \(\Sigma\) 外提
:::info[公式]
\[\begin{aligned}
\sum_{i=1}^n\sum_{j=1}^m\sum_{k|i且k|j}f(k)
&=\sum_{k=1}^{\min(n,m)}\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}f(k)\\
&=\sum_{k=1}^{\min(n,m)}f(k)\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor} 1\\
&=\sum_{k=1}^{\min(n,m)}f(k)\lfloor\frac{n}{k}\rfloor\lfloor\frac{m}{k}\rfloor
\end{aligned}\]
:::
公式三：外提因子
:::info[公式]
\[\gcd(i,j)=\sum_{p=1}^{min(n,m)}[\gcd(i,j)=p]
\]
:::
公式四：欧拉反演
:::info[公式]
\[\gcd(i,j)=\sum_{p|i
\operatorname{and}
p|j
}\varphi(p)\]
:::
例题
P1390 公约数的和
题解
:::info[推导]
\[\begin{aligned}
\sum_{i=1}^n\sum_{j=i+1}^n\gcd(i,j)
&=\frac{(\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j))-\frac{(n)(n-1)}{2}}{2}
\end{aligned}
\]
\[\begin{aligned}
\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)
&=\sum_{i=1}^n\sum_{j=1}^n\sum_{d=1}^nd[\gcd(i,j)=d]\\
&=\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^nd[\gcd(i,j)=d]\\
&=\sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}d[\gcd(i,j)=1]\\
&=\sum_{d=1}^n\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{i=1}^{\lfloor\frac{n}{dp}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{dp}\rfloor}d\mu(p)\\
&=\sum_{d=1}^n\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}d\mu(p)\sum_{i=1}^{\lfloor\frac{n}{dp}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{dp}\rfloor}1\\
&=\sum_{d=1}^n\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}d\mu(p)(\lfloor\frac{n}{dp}\rfloor)^2\\
\end{aligned}\]
设 \(T=dp\)，则
\[\begin{aligned}
\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)&=\sum_{d=1}^n\sum_{p=1}^{\lfloor\frac{n}{d}\rfloor}d\mu(p)(\lfloor\frac{n}{dp}\rfloor)^2\\
&=\sum_{T=1}^n\sum_{p|T}p\mu(\frac{T}{p})(\lfloor\frac{n}{T}\rfloor)^2\\
&=\sum_{T=1}^n(\lfloor\frac{n}{T}\rfloor)^2\sum_{p|T}p\mu(\frac{T}{p})
&=\sum_{T=1}^n(\lfloor\frac{n}{T}\rfloor)^2\varphi(T)
\end{aligned}\]
:::
std
:::info[代码]
#include <bits/stdc++.h>
#define int long long
using namespace std;
int book[2000005],prime[1000005],pnum,phi[2000005],n;
int ans[2000005];
signed main()
{cin>>n;phi[1]=1;for(int i=2;i<=n;i++){if(!book[i]){prime[++pnum]=i;phi[i]=i-1;}for(int j=1;j<=pnum&&i*prime[j]<=n;j++){book[i*prime[j]]=1;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}phi[i*prime[j]]=phi[i]*phi[prime[j]];}}for(int i=1;i<=n;i++)ans[i]=ans[i-1]+phi[i];for(int i=1;i<=n;i++)ans[i]=ans[i]*2-1;int ret=0;for(int i=1;i<=n;i++){ret+=i*ans[n/i];}cout<<(ret-n*(n+1)/2)/2;return 0;
}
:::
P3327 [SDOI2015] 约数个数和
题解
:::info[推导]
\[\begin{aligned}
\sum^n_{i=1}
\sum^m_{j=1}
d(ij)
&=
\sum^n_{i=1}
\sum^m_{j=1}
\sum_{k|i}
\sum_{l|j}
[\gcd(k,l)=1]\\
&=
\sum^n_{i=1}
\sum^m_{j=1}
\sum_{k|i}
\sum_{l|j}
\varepsilon(\gcd(k,l)=1)\\
&=
\sum^n_{i=1}
\sum^m_{j=1}
\sum_{k|i}
\sum_{l|j}
\sum_{p|k \operatorname{and} p|l}
\mu(p)\\
&=
\sum^n_{k=1}
\sum^m_{l=1}
\sum^{\lfloor\frac n k\rfloor}_{i=1}
\sum^{\lfloor\frac m l\rfloor}_{j=1}
\sum_{p|k \operatorname{and} p|l}
\mu(p)\\
&=
\sum^n_{k=1}
\sum^m_{l=1}
\sum_{p|k \operatorname{and} p|l}
\sum^{\lfloor\frac n k\rfloor}_{i=1}
\sum^{\lfloor\frac m l\rfloor}_{j=1}
\mu(p)\\
&=
\sum^n_{k=1}
\sum^m_{l=1}
\sum_{p|k \operatorname{and} p|l}
\lfloor\frac n k\rfloor
\lfloor\frac m l\rfloor
\mu(p)\\
&=
\sum^{\min(n,m)}_{p=1}
\sum^{\lfloor\frac n p\rfloor}_{k=1}
\sum^{\lfloor\frac m p\rfloor}_{l=1}
\lfloor\frac n {kp}\rfloor
\lfloor\frac m {lp}\rfloor
\mu(p)\\
&=
\sum^{\min(n,m)}_{p=1}
\mu(p)
\sum^{\lfloor\frac n p\rfloor}_{k=1}
\sum^{\lfloor\frac m p\rfloor}_{l=1}
\lfloor\frac n {kp}\rfloor
\lfloor\frac m {lp}\rfloor\\
&=
\sum^{\min(n,m)}_{p=1}
\mu(p)
\sum^{\lfloor\frac n p\rfloor}_{k=1}
\lfloor\frac n {kp}\rfloor
\sum^{\lfloor\frac m p\rfloor}_{l=1}
\lfloor\frac m {lp}\rfloor\\
\end{aligned}
\]
我们只需数论分块预处理出 $ \displaystyle
\sum^{\lfloor\frac n p\rfloor}{k=1}
\lfloor\frac n {kp}\rfloor \(
与
\) \displaystyle\sum^{\lfloor\frac m p\rfloor}
\lfloor\frac m {lp}\rfloor
$ 即可。
:::
std
:::info[代码]
#include<bits/stdc++.h>
using namespace std;
int mu[100005],prime[100005],pnum,book[100005],s[100005];
long long clac(int n){int l=0,r=0;long long ret=0;for(;;){if(r>=n)break;l=r+1;r=n/(n/l);r=min(r,n);ret+=(r-l+1)*(n/l);}return ret;
}
long long f(int n,int m){int l=0,r=0;long long ret=0;for(;;){if(r>=n||r>=m)break;l=r+1;r=min(n/(n/l),m/(m/l));r=min(r,n);r=min(r,m);ret+=(long long)(mu[r]-mu[l-1])*s[n/l]*s[m/l];}return ret;
}
int main(){mu[1]=1;for(int i=1;i<=50000;i++){s[i]=clac(i);}for(int i=2;i<=100000;i++){if(!book[i]){prime[++pnum]=i;mu[i]=-1;}for(int j=1;j<=pnum&&i*prime[j]<=100000;j++){book[i*prime[j]]=1;if(i%prime[j]==0){mu[i*prime[j]]=0;break;}mu[i*prime[j]]=-mu[i];}}prime[pnum+1]=0x3f3f3f3f;for(int i=2;i<=100000;i++){mu[i]+=mu[i-1];}int T;cin>>T;while(T--){int a,b;long long ans=0;cin>>a>>b;printf("%lld\n",f(a,b));}return 0;
}
:::
P2257 YY的GCD
题解
:::info[推导]
\[\begin{aligned}
\sum^n_{i=1}
\sum^m_{j=1}
\sum_{k\in \textup{Prime}}
[\gcd(i,j)=k]
&=
\sum_{k\in \textup{Prime}}
\sum^n_{i=1}
\sum^m_{j=1}
[\gcd(i,j)=k]\\
&=
\sum_{k\in \textup{Prime}}
\sum^{\lfloor\frac n k\rfloor}_{i=1}
\sum^{\lfloor\frac m k\rfloor}_{j=1}
[\gcd(i,j)=1]\\
&=
\sum_{k\in \textup{Prime}}
\sum^{\lfloor\frac n k\rfloor}_{i=1}
\sum^{\lfloor\frac m k\rfloor}_{j=1}
\varepsilon(\gcd(i,j))\\
&=
\sum_{k\in \textup{Prime}}
\sum^{\lfloor\frac n k\rfloor}_{i=1}
\sum^{\lfloor\frac m k\rfloor}_{j=1}
\sum_{p|i\operatorname{and}p|j}
\mu(p)\\
&=
\sum^{\min(n,m)}_{p=1}
\sum_{k\in \textup{Prime}}
\sum^{\lfloor\frac n {kp}\rfloor}_{i=1}
\sum^{\lfloor\frac m {kp}\rfloor}_{j=1}
\mu(p)\\
&=
\sum^{\min(n,m)}_{p=1}
\sum_{k\in \textup{Prime}}
\lfloor\frac n {kp}\rfloor
\lfloor\frac m {kp}\rfloor
\mu(p)\\
&=
\sum^{\min(n,m)}_{p=1}
\mu(p)
\sum_{k\in \textup{Prime}}
\lfloor\frac n {kp}\rfloor
\lfloor\frac m {kp}\rfloor\\
\end{aligned}
\]
设 \(kp=T\)，则：
\[\begin{aligned}
\sum^n_{i=1}
\sum^m_{j=1}
\sum_{k\in \textup{Prime}}
[\gcd(i,j)=k]
&=
\sum^{\min(n,m)}_{T=1}
\sum_{k\in \textup{Prime}}
\mu(\lfloor\frac T k\rfloor)
\lfloor\frac n T\rfloor
\lfloor\frac m T\rfloor\\
&=
\sum^{\min(n,m)}_{T=1}
\lfloor\frac n T\rfloor
\lfloor\frac m T\rfloor
\sum_{k|T \operatorname{and} k\in \textup{Prime}}
\mu(\lfloor\frac T k\rfloor)\\
\end{aligned}
\]
:::
P4980 【模板】Pólya 定理
一切空间、平面、群等数学名词，都是纸老虎满足特定性质的集合。
题解：
:::info[推导]
题意：求
\[\frac 1n\sum^{n}_{i=1}k^{\gcd(i,n)}
\]
\[\begin{aligned}
\frac 1n\sum^{n}_{i=1}k^{\gcd(i,n)}
&=\frac 1n\sum^{n}_{i=1}\sum^{n}_{p=1}k^p[\gcd(i,n)=p]\\
&=\frac 1n\sum_{p|n}k^p\sum^{n}_{i=1}[\gcd(i,n)=p]\\
&=\frac 1n\sum_{p|n}k^p\sum^{\frac np}_{i=1}[\gcd(i,\frac np)=1]\\
&=\frac 1n\sum_{p|n}k^p\varphi(\frac n p)\\
\end{aligned}\]
:::
std
:::info[代码]
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MX=3000000,mod=1e9+7;
int qpow(int x,int y){if(y==0)return 1;if(y==1)return x;int z=qpow(x,y/2);z=z*z%mod;if(y&1)z=z*x%mod;return z;
}
int phi(int x){int ret=x;for(int i=2;i*i<=x;i++){if(x%i==0){while(x%i==0)x/=i;ret=ret/i*(i-1);}}if(x>1)ret=ret/x*(x-1);return ret;
}
signed main(){int T,n;T,n,cin>>T;while(T--){int n;cin>>n;int c=sqrt(n);int ans=0;for(int i=1;i<=c;i++){if(n%i==0){ans+=qpow(n,i-1)*phi(n/i)%mod;int j=n/i;if(j!=i)ans+=qpow(n,j-1)*phi(n/j)%mod;ans%=mod;}}cout<<ans<<endl;}return 0;
}
:::
T536265 GLOI-买项链
题解
板子题（洛谷上的 AHOI 懒得写高精
代码
:::info[代码]
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int n,k,a[1005][1005],b[1005][1005],c[1005][1005],d[1005][1005],cnt,ans;
int qpow(int x,int y){if(y==0)return 1;if(y==1)return x;int z=qpow(x,y/2);z=z*z%mod;if(y&1)z=z*x%mod;return z;
}
bool pd(){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(a[i][j]!=b[i][j])return 0;}}return 1;
}
bool pd2(){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(a[i][j]!=c[i][j])return 0;}}return 1;
}signed main() {cnt=0;ans=0;
// scanf("%lld%lld",&n,&k);cin>>n>>k;int bl=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d",&a[i][j]);if(a[i][j])bl++;}}for(int j=n,k=1;j>=1;j--,k++){for(int i=1;i<=n;i++){d[k][i]=a[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){c[i][j]=a[n-i+1][n-j+1];}}for(int j=1;j<=n;j++){for(int i=n,k=1;i>=1;i--,k++){b[j][k]=a[i][j];}}if(pd()){ans+=2*qpow(k,(bl+3)/4);cnt+=2;}if(pd2()){ans+=qpow(k,(bl+1)/2);cnt++;}ans+=qpow(k,bl);cnt++;ans%=mod;printf("%lld",ans*qpow(cnt,mod-2)%mod);
// puts("");
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++)
// printf("%d ",b[i][j]);
// puts("");
// }
// puts("");
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++)
// printf("%d ",c[i][j]);
// puts("");
// }
// puts("");
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++)
// printf("%d ",d[i][j]);
// puts("");
// }return 0;
}/*
11 11
1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0 1 0 1
*/
:::
P4727 [HNOI2009] 图的同构计数
题解
:::info[推导]
有意思的题++
考虑将题意转化为完全图的边染成 \(2\) 种颜色（存在或不存在）。则可以构造出置换群：
\[\begin{pmatrix}
1\ 2\dots\frac{n(n-1)}{2}\\
b_1\ b_2\dots b_\frac{n(n-1)}{2}
\end{pmatrix}\]
其中 \(b\) 为 \(1\sim\frac{n(n-1)}{2}\) 的一个排列。
对于当前排列，如何计算方案数？
直接上 Pólya 时间复杂度爆炸，所以这里有一个奇怪（？）的套路：枚举该群的子群长度，子群长度都相等的置换群贡献相同。
如 \(n=4\) 时，群长度为 \(6\)，就可以分为 \((1,1,1,1,1,1),(2,1,1,1,1),(2,2,1,1),(2,2,2),(3,1,1,1),(3,2,1),(3,3),(4,1,1),(4,2),(5,1),(6)\) 这 \(11\) 种排列。设排列 \((b_1,b_2,\dots,b_k)\)，则易得排列的重复数为 \(\prod b\)，但会有相同的 \(b\)，所以答案还需除以 \(\prod p!\)（\(p_i\) 表示 \(i\) 在 \(b\) 中出现次数）。
但会出现一个 Venti 问题：时间复杂度仍逼近 \(O(n^2!)\)（虽然常数极小）。
我们尝试更改置换群
\(\begin{pmatrix}
b_1\ b_2\dots b_k
\end{pmatrix}\)
使其表示点的状态。
如何统计边的状态数呢？
我们考虑把边分成两类：
两端点在同一置换内
由于相邻的点都等价，两边等价当且仅当两端点在集合中的距离不同（想象将集合排成一个圆），所以集合内的边对状态的贡献为 \(\sum\lfloor\frac{b_i}{2}\rfloor\)
两端点在不同置换内
由于相邻的点都等价，我们可以想象一次置换是“旋转”置换群一次，那么旋转之后和原边相等的边自然就有贡献。我们来一组群：
\[\begin{pmatrix}
1\ 2\ 3\\
2\ 3\ 1\\
\end{pmatrix}
\begin{pmatrix}
1\ 2\ 3\ 4\\
2\ 3\ 4\ 1\\
\end{pmatrix}\]
会发现边 \(1,1\) 旋转之后会变成 \(3,4\)，等价于边 \(1,2\)，再旋转得 \(1,3\)，再得 \(1,1\)，即每一条边都为相同置换。
那怎么统计呢？我们再来一组群：
\[\begin{pmatrix}
1\ 2\ 3\ 4\ 5\ 6\\
2\ 3\ 4\ 5\ 6\ 1
\end{pmatrix}
\begin{pmatrix}
1\ 2\ 3\ 4\\
2\ 3\ 4\ 1\\
\end{pmatrix}\]
会发现边 \(1,1\) 旋转之后会变成 \(4,6\)，等价于边 \(1,3\)，在旋转就变成 \(1,5\)，在旋转变会 \(1,1\)，会发现置换集合大小只有 \(3\)，即有 \(2\) 种置换。
通过这两组数据，我们会发现，旋转加的数为 \(\gcd(b_i,b_j)\)，这也是置换的数量。（可以 CRT 证明）
于是群之间的贡献为 \(\sum^m_{i=1}\sum^{i-1}_{j=1}\gcd(b_i,b_j)\)，解决！
最后具体做法是枚举 \(b\) 数组，答案加上
\[\frac{2^{\sum^m_{i=1}\sum^{i-1}_{j=1}\gcd(b_i,b_j)+\sum_{i=1}^m\lfloor\frac{b_i}{2}\rfloor}}{\prod^{m}_{i=1}b_i\prod^{60}_1p_i}
\]
需要预处理 GCD，否则会被卡常QAQ
:::
代码
:::info[代码]
#include<bits/stdc++.h>
using namespace std;
#define ls (id * 2)
#define rs (id * 2 + 1)
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
int n,d[105],mu,b[105],mul[105],GCD[105][105];
ll ans;
const int mod=997;
ll qpow(ll x,ll y){if(y==1)return x;if(y==0)return 1;ll z=qpow(x,y/2);z=z*z%mod;if(y&1)z=z*x%mod;return z;
}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);
}
ll inv(ll x){return qpow(x,mod-2);
}
void Polya(int m){ll ret=0,r2=1,r3=1;memset(b,0,sizeof(b));for(int i=1;i<=m;i++){
// printf("%d ",d[i]);r2=r2*d[i]%mod;b[d[i]]++;ret+=d[i]/2;}for(int i=1;i<=60;i++){r3=r3*mul[b[i]]%mod;}for(int i=1;i<=m;i++){for(int j=1;j<i;j++){ret+=GCD[d[i]][d[j]];}}ans=(ans+qpow(2,ret)*inv(r2)%mod*inv(r3))%mod;
}
void dfs(int x,int sum,int minn){if(sum==0){Polya(x-1);return;}
// if(minn*x>sum)return;for(int i=1;i<=minn&&i<=sum;i++){d[x]=i;dfs(x+1,sum-i,i);}
}
int main() {cin>>n;mul[0]=1;for(int i=1;i<=n;i++)mul[i]=mul[i-1]*i%mod;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)GCD[i][j]=gcd(i,j);dfs(1,n,n);cout<<ans%mod;return 0;
}:::
拓展：杜教筛
理论部分：
杜教筛，顾名思义，是由杜教（杜瑜皓）dalao 首次应用在中国 OI/ACM 竞赛界的。
杜教筛是用于在小于 \(O(n)\) 的时间内求积性函数前缀和的一种邪道算法。
具体的，对于
$ \displaystyle\sum^{n}{i=1}f(i)$
杜教筛会构造两个函数 \(g,h\) 使得 \(f*g=h\)，再使用莫比乌斯反演与狄利克雷卷积的一些公式或性质，推出形如 $ \displaystyle s(n)=\sum^nc(i)-s(\lfloor\frac{n}{i}\rfloor)$ 的递推式。（其中 \(\displaystyle s(n)=\sum^{n}_{i=1}f(i)\)，\(c(i)\) 为可以 \(O(1)\) 求解的线性函数）
P4213 【模板】杜教筛
题解
:::info[推导]
对于这道题，我们需要构造 \(\mu*g=h\) 以及 \(\varphi*g=h\)。如何构造 \(g\) 与 \(h\) 呢？
跳转至上文“莫比乌斯反演核心函数”部分，我们看到这两个公式：
\[\varphi*1=id
\]
\[\mu*1=\varepsilon
\]
然后构造就完成了。
求 \(\mu\) 函数前缀和
记 \(\displaystyle S(n)=\sum^n_{i=1}\mu(i)\)。
因为 \(\mu*1=\varepsilon\)
所以 \(\displaystyle \sum^n_{i=1}\varepsilon(i)=\sum^n_{i=1}\sum_{j|i}\mu(j)\)
\[\sum^n_{i=1}\varepsilon(i)=\sum^n_{j=1}\sum^{\lfloor\frac n j\rfloor}_{i=1}\mu(j)
\]
\[1=\sum^n_{j=1}S(\lfloor\frac n j\rfloor)
\]
我们将 \(j=1\) 一项提取出来，得：
\[1=S(n)+\sum^n_{j=2}S(\lfloor\frac n j\rfloor)
\]
移项，得：
\[S(n)=1-\sum^n_{j=2}S(\lfloor\frac n j\rfloor)
\]
求 \(\varphi\) 函数前缀和
记 \(\displaystyle S(n)=\sum^n_{i=1}\varphi(i)\)。
因为 \(\varphi*1=id\)
所以 \(\displaystyle \sum^n_{i=1}id(i)=\sum^n_{i=1}\sum_{j|i}\varphi(j)\)
\[\sum^n_{i=1}id(i)=\sum^n_{j=1}\sum^{\lfloor\frac n j\rfloor}_{i=1}\varphi(j)
\]
\[\frac{n(n-1)}{2}=\sum^n_{j=1}S(\lfloor\frac n j\rfloor)
\]
我们将 \(j=1\) 一项提取出来，得：
\[\frac{n(n-1)}{2}=S(n)+\sum^n_{j=2}S(\lfloor\frac n j\rfloor)
\]
移项，得：
\[S(n)=\frac{n(n-1)}{2}-\sum^n_{j=2}S(\lfloor\frac n j\rfloor)
\]
:::
std
:::info[代码]
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MX=3000000;
int mu[MX+5],phi[MX+5],book[MX+5],prime[MX+5],pnum;
unordered_map<int,int> mm,mp;
int summu(int x){if(x<=MX)return mu[x];if(mm[x])return mm[x];int l=1,r=1,ret=1;while(1){l=r+1,r=x/(x/l);if(r>x)r=x;ret-=(r-l+1)*summu(x/l);if(r==x)break;}mm[x]=ret;return ret;
}
int sumphi(int x){if(x<=MX)return phi[x];if(mp[x])return mp[x];int l=1,r=1,ret=x*(x+1)/2;while(1){l=r+1,r=x/(x/l);if(r>x)r=x;ret-=(r-l+1)*sumphi(x/l);if(r==x)break;}mp[x]=ret;return ret;
}
signed main(){int T,n;T,n,cin>>T;mu[1]=1;phi[1]=1;for(int i=2;i<=MX;i++){if(!book[i]){prime[++pnum]=i;mu[i]=-1;phi[i]=i-1;}for(int j=1;j<=pnum&&i*prime[j]<=MX;j++){book[i*prime[j]]=1;if(i%prime[j]==0){mu[i*prime[j]]=0;phi[i*prime[j]]=phi[i]*prime[j];break;}mu[i*prime[j]]=-mu[i];phi[i*prime[j]]=phi[i]*phi[prime[j]];}}for(int i=2;i<=MX;i++){mu[i]+=mu[i-1];phi[i]+=phi[i-1];}while(T--){cin>>n;printf("%lld %lld\n",sumphi(n),summu(n)); }return 0;
}:::
P6055 [RC-02] GCD
题解
:::info[推导]
很巧妙的转换消元。
\[\begin{aligned}
\sum^n_{i=1}
\sum^n_{j=1}
\sum^{\lfloor\frac{n}{j}\rfloor}_{p=1}
\sum^{\lfloor\frac{n}{j}\rfloor}_{q=1}
[\gcd(i,j)=1][\gcd(p,q)=1]
&=
\sum^n_{i=1}
\sum^n_{j=1}
\sum^{n}_{p=1}
\sum^{n}_{q=1}
[\gcd(i,j)=1][\gcd(p,q)=j]\\
&=
\sum^n_{i=1}
\sum^{n}_{p=1}
\sum^{n}_{q=1}
[\gcd(i,p,q)=1]\\
&=
\sum^n_{i=1}
\sum^{n}_{p=1}
\sum^{n}_{q=1}
[\varepsilon(\gcd(i,p,q))]\\
&=
\sum^n_{i=1}
\sum^{n}_{p=1}
\sum^{n}_{q=1}
\sum_{k|i\operatorname{and}k|p\operatorname{and}k|q}
\mu(k)\\
&=
\sum^n_{k=1}
\sum^{\lfloor\frac{n}{k}\rfloor}_{i=1}
\sum^{\lfloor\frac{n}{k}\rfloor}_{p=1}
\sum^{\lfloor\frac{n}{k}\rfloor}_{q=1}
\mu(k)\\
&=
\sum^n_{k=1}
\lfloor\frac{n}{k}\rfloor^3
\mu(k)\\
\end{aligned}
\]
然后套杜教筛+数论分块就可以了~
:::
std
:::info[代码]
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MX=3000000;
const int modx=998244353;
int mu[MX+5],book[MX+5],prime[MX+5],pnum;
unordered_map<int,int> mm;
int summu(int x){if(x<=MX)return mu[x];if(mm[x])return mm[x];int l=1,r=1,ret=1;while(1){l=r+1,r=x/(x/l);if(r>x)r=x;ret-=(r-l+1)*summu(x/l);if(r==x)break;}mm[x]=ret;return ret;
}
int getans(int x){int l=0,r=0,ret=0;while(1){l=r+1;r=x/(x/l);r=min(r,x);int c=summu(r)-summu(l-1);c%=modx;c*=x/l;c%=modx;c*=x/l;c%=modx;c*=x/l;c%=modx;ret=(ret+c)%modx;if(r==x)break;}return ret;
}
signed main(){int n;mu[1]=1;for(int i=2;i<=MX;i++){if(!book[i]){prime[++pnum]=i;mu[i]=-1;}for(int j=1;j<=pnum&&i*prime[j]<=MX;j++){book[i*prime[j]]=1;if(i%prime[j]==0){mu[i*prime[j]]=0;break;}mu[i*prime[j]]=-mu[i];}}for(int i=2;i<=MX;i++){mu[i]+=mu[i-1];}cin>>n;cout<<(getans(n)+modx)%modx; return 0;
}
:::
P3768 简单的数学题
题解
:::info[推导]
\[\begin{aligned}
\sum^n_{i=1}
\sum^n_{j=1}
ij\gcd(i,j)
&=
\sum^n_{i=1}
\sum^n_{j=1}
ij
\sum_{p|i\^{\ \ }p|j}\varphi(p)
\\
&=
\sum^n_{p=1}
\sum^{\lfloor\frac{n}{p}\rfloor}_{i=1}
\sum^{\lfloor\frac{n}{p}\rfloor}_{j=1}
ijp^2\varphi(p)
\\
&=
\sum^n_{p=1}
p^2\varphi(p)sum(\lfloor\frac{n}{p}\rfloor)
\\
\end{aligned}
\]
其中
\[\begin{aligned}
sum(x)
&=\sum^{x}_{i=1}
\sum^{x}_{j=1}ij\\
&=\frac{(x+1)^2x^2}{4}
\end{aligned}
\]
感觉有题解做复杂了呢，还化成了 \(\mu\)。
数论分块即可……等等，\(n\le10^{10}\)？
也就是说，我们要在小于 \(O(n)\) 的复杂度内求出所有 \(p^2\varphi(p)\)。
考虑杜教筛。
设 \(f(x)=x^2\varphi(x)\)，有函数 \(g,h\)，满足 \(f*g=h\)。
那么，有：
\[\sum_{p|n}f(p)g(\frac{n}{p})=h(n)
\]
\[\sum_{p|n}p^2\varphi(p)g(\frac{n}{p})=h(n)
\]
这个 \(p^2\) 不好处理 ，我们考虑把它消掉。
注意到，\(p\times\frac{n}{p}=n\)。
于是，我们考虑再设 \(g'(x)=x^2g'(x)\)
\[\begin{aligned}
\sum_{p|n}p^2\varphi(p)(\frac{n}{p})^2g'(\frac{n}{p})&=h(n)\\
\sum_{p|n}n^2\varphi(p)g'(\frac{n}{p})&=h(n)\\
n^2\sum_{p|n}\varphi(p)g'(\frac{n}{p})&=h(n)
\end{aligned}
\]
我们考虑设 \(h'(x)=x^2h(x)\)
\[\begin{aligned}
n^2\sum_{p|n}\varphi(p)g'(\frac{n}{p})&=n^2h'(n)\\
\sum_{p|n}\varphi(p)g'(\frac{n}{p})&=h'(n)
\end{aligned}
\]
此时，我们易得：
\[\begin{aligned}
g'(x)&=1\\
h'(x)&=x\\
\end{aligned}
\]
也就是原来的：
\[\begin{aligned}
g(x)&=x^2\\
h(x)&=x^3\\
\end{aligned}
\]
于是，就可以杜教筛了。
我们设 \(S(x)=\sum_{i=1}^x f(x)\)
\[\begin{aligned}
\sum_{i=1}^x \sum_{p|i}p^2\varphi(p)(\frac{i}{p})^2&=\sum_{i=1}^xi^3\\
\sum_{i=1}^x i^2
\sum_{p|i}\varphi(p)&=\sum_{i=1}^xi^3\\\sum_{p=1}^xp^2\sum_{i=1}^{\lfloor\frac{x}{p}\rfloor}
\varphi(i)&=\sum_{i=1}^xi^3\\\sum_{p=1}^xp^2\sum_{i=1}^{\lfloor\frac{x}{p}\rfloor}
\varphi(i)&=\sum_{i=1}^xi^3\\\sum_{p=1}^xp^2S(\lfloor\frac{x}{p}\rfloor)
&=\sum_{i=1}^xi^3\\S(x)+\sum_{p=2}^xp^2S(\lfloor\frac{x}{p}\rfloor)
&=\sum_{i=1}^xi^3\\
S(x)
&=\sum_{i=1}^xi^3-\sum_{p=2}^xp^2S(\lfloor\frac{x}{p}\rfloor)\\
S(x)
&=\frac{x^2(x+1)^2}{4}-\sum_{p=2}^xp^2S(\lfloor\frac{x}{p}\rfloor)\end{aligned}
\]
完成！
但是这要做 \(O(\sqrt n)\) 次杜教筛，不会TLE吗？
冷知识：一次杜教筛不止筛一个数。实际上，它会把每个 \(\frac{x}{p}\) 都筛到，也就是说，我们只需要筛一遍，就可以找出所有需要的 \(S\) 了。
:::
std
:::info[代码]
#include<bits/stdc++.h>
#define int __int128
#define _2(x) ((x)*(x)%mod)
using namespace std;
typedef long long ll;
const int MX=5000000;
ll mod,inv6;
int mu[MX+5],phi[MX+5],book[MX+5],prime[MX+5],pnum;
unordered_map<ll,ll>mp;
int qpow(int x,int y){if(y==0)return 1;int z=qpow(x,y/2);z=z*z%mod;if(y&1)z=z*x%mod;return z;
}
int inv(int x){return qpow(x,mod-2);
}
int sum(__int128 x){return _2(x*(x+1)/2%mod);
}
int sum2(__int128 x){return (x*(x+1)%mod*(2*x+1)%mod*inv6%mod);
}
int sumphi(int x){if(x<=MX)return phi[x];if(mp[x])return mp[x];int l=1,r=1,ret=x*(x+1)/2%mod;ret=ret*ret%mod;while(1){l=r+1,r=x/(x/l);if(r>x)r=x;ret-=(sum2(r)-sum2(l-1))*sumphi(x/l)%mod;ret%=mod;if(r==x)break;}ret+=mod;ret%=mod;mp[x]=ret;return ret;
}
ll calc(int x){int l=1,r=0,ret=0;sumphi(x);while(1){l=r+1,r=x/(x/l);if(r>x)r=x;ret=ret+(sumphi(r)-sumphi(l-1))*sum(x/l)%mod;ret%=mod;if(r==x)return (ret+mod)%mod;}
}
signed main(){int T;ll n;cin>>mod;inv6=inv(6);mu[1]=1;phi[1]=1;for(int i=2;i<=MX;i++){if(!book[i]){prime[++pnum]=i;mu[i]=-1;phi[i]=i-1;}for(int j=1;j<=pnum&&i*prime[j]<=MX;j++){book[i*prime[j]]=1;if(i%prime[j]==0){mu[i*prime[j]]=0;phi[i*prime[j]]=phi[i]*prime[j];break;}mu[i*prime[j]]=-mu[i];phi[i*prime[j]]=phi[i]*phi[prime[j]];}}for(int i=2;i<=MX;i++){mu[i]+=mu[i-1];phi[i]=(phi[i-1]+i*i%mod*phi[i]%mod)%mod;}cin>>n;printf("%lld\n",calc(n)); return 0;
}
:::
P9238 [蓝桥杯 2023 省 A] 翻转硬币
题解
:::info[题解]
观察得：答案是 \(\sum^{n}_{i=1}|\mu(i)|\)。
继续观察，容斥，答案是 \(\sum^{\sqrt n}_{i=1}\mu(i)\frac{n}{i^2}\)。
注意到，这个可以数论分块，再加杜教筛处理 \(\mu\) 和即可通过本题。
:::
std
:::info[代码]
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MX=10000000;
int mu[MX+5],phi[MX+5],book[MX+5],prime[MX+5],pnum;
unordered_map<int,int> mm,mp;
int summu(int x){if(x==0)return 0;if(x<=MX)return mu[x];if(mm[x])return mm[x];int l=1,r=1,ret=1;while(1){l=r+1,r=x/(x/l);if(r>x)r=x;ret-=(r-l+1)*summu(x/l);if(r==x)break;}mm[x]=ret;return ret;
}
int sumphi(int x){if(x<=MX)return phi[x];if(mp[x])return mp[x];int l=1,r=1,ret=x*(x+1)/2;while(1){l=r+1,r=x/(x/l);if(r>x)r=x;ret-=(r-l+1)*sumphi(x/l);if(r==x)break;}mp[x]=ret;return ret;
}
int T,n;
int calc(){int l=0,r=0,ret=0,sq=sqrt(n);summu(sqrt(n));while(1){l=r+1;if(l*l>n)break;r=sqrt(n/(n/(l*l)));
// printf("%d %d %d %d\n",l,r,n/(l*l),n/(r*r));if(r*r>n)r=sq;ret+=(n/(l*l))*(summu(r)-summu(l-1));}return ret;
}
signed main(){mu[1]=1;phi[1]=1;for(int i=2;i<=MX;i++){if(!book[i]){prime[++pnum]=i;mu[i]=-1;phi[i]=i-1;}for(int j=1;j<=pnum&&i*prime[j]<=MX;j++){book[i*prime[j]]=1;if(i%prime[j]==0){mu[i*prime[j]]=0;phi[i*prime[j]]=phi[i]*prime[j];break;}mu[i*prime[j]]=-mu[i];phi[i*prime[j]]=phi[i]*phi[prime[j]];}}long long ans;cin>>n;for(int i=2;i<=MX;i++){mu[i]+=mu[i-1];phi[i]+=phi[i-1];}
// summu(sqrt(n));ans=0;
// for(long long i=1;i<=n;i++){
// if(mu[i])
// ans++;
// }
// for(long long i=1;i*i<=n;i++){
// ans+=mu[i]*(n/(i*i));
// }cout<<calc();return 0;
}
:::