没时间了，记几个公式好了。
令 \(S(n)=\sum_{i=1}^nf(i)\)，则 \(g(1)S(n)=\sum_{i=1}^n(f*g)(i)-\sum_{i=\bm 2}^nS(\lfloor\frac ni\rfloor)\)。
e.g.
\(f=\mu,S(n)=\sum_{i=1}^n(\mu*1)(i)-\sum_{i=\bm 2}^nS(\lfloor\frac ni\rfloor)=1-\sum_{i=\bm 2}^nS(\lfloor\frac ni\rfloor)\)；
\(f=\varphi,S(n)=\sum_{i=1}^n(\varphi*1)(i)-\sum_{i=\bm 2}^nS(\lfloor\frac ni\rfloor)={n(n+1)\over 2}-\sum_{i=\bm 2}^nS(\lfloor\frac ni\rfloor)\)。
递归调用即可。注意记忆化。
求 \(\sum \mu\)：
unordered_map<int,int>bk,smu;
int Smu(int n){
if(n<=1e6)return smu[n];
if(bk[n])return smu[n];
bk[n]=1;
int ret=1;
for(int i=2,j;i<=n;i=j+1){
j=n/(n/i);
ret-=(j-i+1)*Smu(n/i);
}
return smu[n]=ret;
}
//main
mu[1]=1;
for(int i=2;i<=1e6;i++){
if(!v[i])mu[i]=-1,p[++n_p]=i;
for(int j=1;j<=n_p&&p[j]*i<=1e6;j++){
v[p[j]*i]=1;
if(i%p[j])mu[i*p[j]]=-mu[i];
else {mu[i*p[j]]=0;break;}
}
}
for(int i=1;i<=1e6;i++)smu[i]=smu[i-1]+mu[i];
复杂度是 \(O(n^{\frac34})\)，通过预处理 \(S(1)\sim S(n^{\frac23})\) 可以做到 \(O(n^{\frac23})\)。证明需要使用高等数学。
【习题1】利用 \(S_1(n)=\sum_{i=1}^n\mu(i)\) 求 \(S_2(n)=\sum_{i=1}^n\varphi(i)\).
不难由莫比乌斯反演推得 \(S_2'(n)=\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=1]=\sum_{d=1}^n\mu(d)\lfloor\frac nd\rfloor^2\)，而 \(S_2'(n)\) 就是除了 \((1,1)\)，每个在 \(S_2(n)\) 中统计过的都统计了两次，所以 \(S_2(n)=(S_2'(n)+1)/2\)。求 \(S_2'(n)\) 可以直接整除分块并调用 Smu()，可证总复杂度不变。
int Sphi(int n){
int ret=0;
for(int i=1,j;i<=n;i=j+1){
j=n/(n/i);
ret+=(n/i)*(n/i)*(Smu(j)-Smu(i-1));
}
return (ret+1)/2;
}
【习题2】
【习题3】[NOI2016]循环之美
设无限循环小数 \(\frac xy\) 的循环节长度为 \(l\)，根据循环小数的小数点右移 \(l\) 位不会导致小数部分的变化，可以列出
等式两边同时乘以 \(y\) 进行等价变形
\[xk^l-\lfloor\frac{xk^l}y\rfloor y=x-\lfloor\frac{x}y\rfloor y \]等号左侧就是 \(xk^l\bmod y\) 的另一种形式，等式右侧同理，由此
\[xk^l\equiv x\pmod y \]当且仅当 \(\gcd(x,y)=1\) 时，上式等价于 \(k^l\equiv 1\pmod y\)。而当且仅当 \(\gcd(k,y)=1\) 时，存在 \(l\) 使此式成立。
综上，只需要统计 \(\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1][\gcd(j,k)=1]\)。
考察 \([\gcd(j,k)=1]\)
\[f(n,m,k)=\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1][\gcd(j,k)=1]\\ =\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1]\sum_{d|j,d|k}\mu(d)\\ =\sum_{d|k}\mu(d)\sum_{i=1}^n\sum_{d|j,j\le m}[\gcd(i,j)=1]\\ =\sum_{d|k}\mu(d)\sum_{i=1}^n\sum_{q=1}^{m/d}[\gcd(i,qd)=1]\\ =\sum_{d|k}\mu(d)\sum_{q=1}^{m/d}\sum_{i=1}^n[\gcd(i,q)=1][\gcd(i,d)=1]\\ =f(m/d,n,d)\]从而可以递推。考虑到 \(d\le k\)，\(m/d\) 也向着减小的方向发展，但 \(d\) 在 \(k=1\) 时就一直保持在 \(1\) 不变了，所以边界是：
- \(f(n,0,k)=f(0,m,k)=0\)
- \(f(n,m,1)=\sum_{d=1}^{\min(n,m)}\mu(d)\lfloor\frac nd\rfloor\lfloor\frac md\rfloor\)
后者直接整除分块计算，但是要用杜教筛处理 \(\sum \mu\)。
实际表现良好，高人证明复杂度为 
。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,m,k,n_p,p[N],mu[N];
bool v[N];
unordered_map<int,int>bk,smu;
int Smu(int n){
if(n<=1e6)return smu[n];
if(bk[n])return smu[n];
bk[n]=1;
int ret=1;
for(int i=2,j;i<=n;i=j+1){
j=n/(n/i);
ret-=(j-i+1)*Smu(n/i);
}
return smu[n]=ret;
}
int f(int n,int m,int k){
if(!n||!m)return 0;
if(k==1){
int ret=0;
for(int i=1,j;i<=min(n,m);i=j+1){
j=min(n/(n/i),m/(m/i));
ret+=(Smu(j)-Smu(i-1))*(n/i)*(m/i);
}
return ret;
}
int ret=0;
for(int i=1;i*i<=k;i++)if(k%i==0){
if(mu[i])ret+=mu[i]*f(m/i,n,i);
if(i*i!=k&&mu[k/i])ret+=mu[k/i]*f(m/(k/i),n,k/i);
}
return ret;
}
signed main(){
mu[1]=1;
for(int i=2;i<=1e6;i++){
if(!v[i])mu[i]=-1,p[++n_p]=i;
for(int j=1;j<=n_p&&p[j]*i<=1e6;j++){
v[p[j]*i]=1;
if(i%p[j])mu[i*p[j]]=-mu[i];
else {mu[i*p[j]]=0;break;}
}
}
for(int i=1;i<=1e6;i++)smu[i]=smu[i-1]+mu[i];
cin>>n>>m>>k;
cout<<f(n,m,k);
}