莫比乌斯反演经典例题回顾

发表于 2018-12-30 更新于 2022-02-14 分类于题解

$\ \ \ \ \ \ \ \,$莫比乌斯反演经典例题回顾，思考和题解：

P2522 [HAOI2011]Problem b

$\sum_{i=a}^b\sum_{j=c}^d[gcd(i,j)=k]$

反演过程：

${F(n,m)=\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=k]}$

$ans=F(a,b)-F(a-1,d)-F(b,c-1)+F(a-1,c-1)$

$F(n,m)=$

$\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{k}\right\rfloor}[gcd(i,j)=1]$

$\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{k}\right\rfloor}ϵ(gcd(i,j)=1)$

$\sum_{d=1}^{\left\lfloor\frac{min(n,m)}{k}\right\rfloor}\sum_{d|T}\mu(d){\left\lfloor\frac{n}{T}\right\rfloor}{\left\lfloor\frac{m}{T}\right\rfloor}$

$\sum_{d=1}^{\left\lfloor\frac{min(n,m)}{k}\right\rfloor}\mu(d){\left\lfloor\frac{n}{kd}\right\rfloor}{\left\lfloor\frac{m}{kd}\right\rfloor}$

$\ \ \ \ \ \,$ $O(n)$预处理$\mu$，每次询问分块，复杂度$O(\sqrt n)$，总复杂度为$O(n+T4\sqrt n)$

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<cmath>
using namespace std;
const int inf=0x7fffffff;
const double eps=1e-10;
const double pi=acos(-1.0);
const int N=50010;
inline int read(){
  int x=0,f=1;char ch;ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
  return x*f;
}
bool vis[N];
int prim[N],mu[N],sum[N],k;
void get_mu(int n){
  mu[1]=1;
  for(int i=2;i<=n;i++){
    if(!vis[i]){mu[i]=-1;prim[++prim[0]]=i;}
    for(int j=1;j<=prim[0]&&i*prim[j]<=n;j++){
      vis[i*prim[j]]=1;
      if(i%prim[j]==0)break;
      else mu[i*prim[j]]=-mu[i];
    }
  }
  for(int i=1;i<=n;i++)
  sum[i]=sum[i-1]+mu[i];
}
long long Ans(int a,int b){
    a/=k;b/=k;
  int max_rep=min(a,b);
  long long ans=0;
  for(int l=1,r;l<=max_rep;l=r+1){
    r=min(a/(a/l),b/(b/l));
    ans+=(long long)(a/l)*(long long)(b/l)*(long long)(sum[r]-sum[l-1]);
  }
  return ans;
}
int main()
{
 	int T=read();
 	get_mu(N-10);
 	while(T--){
 		int a=read(),b=read(),c=read(),d=read();k=read();
 		printf("%lld\n",Ans(b,d)-Ans(b,c-1)-Ans(a-1,d)+Ans(a-1,c-1));
  }
  return 0;
}

P2257 YY的GCD

$\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)\rm\ \ is\ \ prime]$

反演过程：

$\sum_{p=1,[p\rm\ \ is\ \ prime]}\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=p]$

$\sum_{p=1,[p\rm\ \ is\ \ prime]}\sum_{i=1}^{\left\lfloor\frac{n}{p}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{p}\right\rfloor}[gcd(i,j)=1]$

$\sum_{p=1,[p\rm\ \ is\ \ prime]}\sum_{d=1}^{\left\lfloor\frac{min(n,m)}{p}\right\rfloor}\mu(d){\left\lfloor\frac{n}{pd}\right\rfloor}{\left\lfloor\frac{m}{pd}\right\rfloor}$

$\sum_{T=1}^{min(n,m)}\sum_{d|T}\mu(d){\left\lfloor\frac{n}{T}\right\rfloor}{\left\lfloor\frac{m}{T}\right\rfloor}\left[\frac{T}{d}\rm\ \ is\ \ prime\right]$

$\sum_{T=1}^{min(n,m)}{\left\lfloor\frac{n}{T}\right\rfloor}{\left\lfloor\frac{m}{T}\right\rfloor}\sum_{d|T,\left[d\rm\ \ is\ \ prime\right]}\mu\left(\frac{T}{d}\right)$

${F(x)=\sum_{d|x,\left[d\rm\ \ is\ \ prime\right]}\mu\left(\frac{x}{d}\right)}$

${\sum_{T=1}^{min(n,m)}{\left\lfloor\frac{n}{T}\right\rfloor}{\left\lfloor\frac{m}{T}\right\rfloor}F(T)}$

$\ \ \ \ \ \,$ $O(n)$预处理$\mu$，$O(n\log{n})$预处理$F$，每次询问分块，复杂度$O(\sqrt n)$，总复杂度为$O(n\log n+T\sqrt n)$

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<cmath>
using namespace std;
const int inf=0x7fffffff;
const double eps=1e-10;
const double pi=acos(-1.0);
const int N=1e7+10;
inline int read(){
    int x=0,f=1;char ch;ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
bool vis[N];
int prim[N],mu[N];
long long F[N];
void get_mu(int n){
  mu[1]=1;
  for(int i=2;i<=n;i++){
    if(!vis[i]){mu[i]=-1;prim[++prim[0]]=i;}
    for(int j=1;j<=prim[0]&&i*prim[j]<=n;j++){
      vis[i*prim[j]]=1;
      if(i%prim[j]==0)break;
      else mu[i*prim[j]]=-mu[i];
    }
  }
  for(int i=1;i<=prim[0];i++)
  for(int j=1;j*prim[i]<=n;j++)F[j*prim[i]]+=(long long)mu[j];
  for(int i=1;i<=n;i++)F[i]+=F[i-1];
}
long long Ans(int n,int m){
  int lim=min(n,m);
  long long ans=0;
  for(int l=1,r;l<=lim;l=r+1){
    r=min(n/(n/l),m/(m/l));
    ans+=(long long)(n/l)*(long long)(m/l)*(F[r]-F[l-1]);
  }
  return ans;
}
int main()
{
  get_mu(N-10);
  int T=read();
  while(T--){
    int n=read(),m=read();
    printf("%lld\n",Ans(n,m));
  }
  return 0;
}

P3312 [SDOI2014]数表

$\sum_{i=1}^n\sum_{j=1}^m\sum_{k|gcd(i,j)}k\left[\sum_{k|gcd(i,j)}k≤a\right]$

反演过程：

$F(x)=\sum_{i|x}i$

$\sum_{i=1}^n\sum_{j=1}^mF(gcd(i,j))[F(gcd(i,j))≤a]$

$\sum_{d=1}^{min(n,m)}\sum_{i=1}^n\sum_{j=1}^mF(d)[gcd(i,j)=d][F(d)≤a]$

$\sum_{d=1}^{min(n,m)}F(d)[F(d)≤a]\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=d]$

$\sum_{d=1}^{min(n,m)}F(d)[F(d)≤a]\sum_{d’=1}^{\left\lfloor\frac{min(n,m)}{d}\right\rfloor}\mu(d’)\left\lfloor\frac{n}{d’d}\right\rfloor\left\lfloor\frac{m}{d’d}\right\rfloor$

$\sum_{T=1}^{min(n,m)}\sum_{d|T}F(d)\mu\left(\frac{T}{d}\right){\left\lfloor\frac{n}{T}\right\rfloor}{\left\lfloor\frac{m}{T}\right\rfloor}[F(d)≤a]$

$\sum_{T=1}^{min(n,m)}{\left\lfloor\frac{n}{T}\right\rfloor}{\left\lfloor\frac{m}{T}\right\rfloor}\sum_{d|T}F(d)\mu\left(\frac{T}{d}\right)[F(d)≤a]$

$f(x)=\sum_{d|T}F(d)\mu\left(\frac{T}{d}\right)[F(d)≤a]$

$\sum_{T=1}^{min(n,m)}{\left\lfloor\frac{n}{T}\right\rfloor}{\left\lfloor\frac{m}{T}\right\rfloor}f(T)$

$\ \ \ \ \ \,$ $O(n\log n)$预处理$F$和$\mu$，把每次询问的$a$值离线排序，用树状数组维护$f$，花费时间$O(n\log ^2n)$，询问分块，复杂度$O(\sqrt n\log n)$，总时间复杂度$O(n\log ^2n+T\sqrt n\log n)$

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
const int inf=0x7fffffff;
const double eps=1e-10;
const double pi=acos(-1.0);
//char buf[1<<15],*S=buf,*T=buf;
//char getch(){return S==T&&(T=(S=buf)+fread(buf,1,1<<15,stdin),S==T)?0:*S++;}
inline int read(){
  int x=0,f=1;char ch;ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-') f=0;ch=getchar();}
  while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch&15);ch=getchar();}
  if(f)return x;else return -x;
}
const int N=1e5+10;
const int Q=2e4+10;
int sum[N];
bool vis[N];
int prim[N],mu[N];
int S=1;
struct Sum{int data,id;}F[N];
bool operator <(Sum a,Sum b){return a.data<b.data;}
int ans[Q];
#define lowbit(x) ((x)&(-x))
void add(int i,int c)
{for(;i<=N-5;i+=lowbit(i))sum[i]+=c;}
int query(int i){
  int ans=0;
  for(;i;i-=lowbit(i))ans+=sum[i];
  return ans;
}
void Add(int i,int data){
  int ed=((N-5)/i);
  for(register int j=1;j<=ed;++j)
  add(i*j,data*mu[j]);
}
void init(){
  mu[1]=1;
  for(register int i=2;i<=N-5;++i){
    if(!vis[i]){mu[i]=-1;prim[++prim[0]]=i;}
    for(register int j=1;j<=prim[0]&&i*prim[j]<=N-5;++j){
      vis[i*prim[j]]=1;
      if(i%prim[j]==0)break;
      else mu[i*prim[j]]=-mu[i];
    }
  }
  for(register int i=1;i<=N-5;++i){
    F[i].id=i;
    int ed=((N-5)/i);
    for(register int j=1;j<=ed;++j)
    F[i*j].data+=i;
  }
  sort(F+1,F+1+N-5);
}
struct Query{int n,m,a,id;}q[Q];
inline bool operator <(const Query &a,const Query &b){return a.a<b.a;}
int main()
{
  int T=read();
  init();
  for(register int i=1;i<=T;i++){
    q[i].n=read();q[i].m=read();q[i].a=read();q[i].id=i;
    if(q[i].n>q[i].m)swap(q[i].n,q[i].m);
  }
  sort(q+1,q+T+1);
  for(register int i=1;i<=T;i++){
    int n=q[i].n,m=q[i].m,a=q[i].a,id=q[i].id;
    while(F[S].data<=a){Add(F[S].id,F[S].data);S++;}
    for(register int l=1,r;l<=n;l=r+1){
      r=min(n/(n/l),(m/(m/l)));
      ans[id]+=(n/l)*(m/l)*(query(r)-query(l-1));
    }
  }
  for(register int i=1;i<=T;i++)printf("%d\n",ans[i]&0x7fffffff);
  return 0;
}

P3704 [SDOI2017]数字表格

$\prod_{i=1}^{n}\prod_{j=1}^{m}f\left(gcd(i,j)\right)$

$\ \ \ \ \ \,$ $f$为斐波拉契序列。

反演过程：

$\prod_{i=1}^{min(n,m)}\prod_{i=1}^{n}\prod_{j=1}^{m}f(d)\left[gcd(i,j)=d\right]$

$\prod_{d=1}^{min(n,m)}f(d)^{\sum_{i=1}^n\sum_{j=1}^{m}\left[gcd(i,j)=d\right]}$

$\prod_{d=1}^{min(n,m)}f(d)^{\sum_{d’=1}^{\left\lfloor\frac{min(n,m)}{d}\right\rfloor}\mu(d’)\left\lfloor\frac{n}{d’d}\right\rfloor\left\lfloor\frac{m}{d’d}\right\rfloor}$

$\prod_{d=1}^{min(n,m)}\prod_{d’=1}^{\left\lfloor\frac{min(n,m)}{d}\right\rfloor}f(d)^{\mu(d’)\left\lfloor\frac{n}{d’d}\right\rfloor\left\lfloor\frac{m}{d’d}\right\rfloor}$

$\prod_{T=1}^{min(n,m)}\prod_{d|T}f(d)^{\mu\left(\frac{T}{d}\right)\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor}$

${C(x)=\prod_{d|T}f(d)^{\mu\left(\frac{T}{d}\right)}}$

$\prod_{T=1}^{min(n,m)}C(T)^{\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor}$

$\ \ \ \ \ \,$ $O(n)$预处理$f$和$\mu$，$O(n\log{n})$预处理$C$，每次询问分块，复杂度$O(\sqrt n \log n)$，总复杂度为$O(n\log n+T\sqrt n \log n)$

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<cmath>
using namespace std;
const int inf=0x7fffffff;
const double eps=1e-10;
const double pi=acos(-1.0);
const int N=1e6+10;
const long long mod=1e9+7;
inline int read(){
    int x=0,f=1;char ch;ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
long long power(long long a,long long b){  
  long long ans=1ll;  
  a=a%mod;
  while(b!=0){  
    if(b&1) ans=(ans*a)%mod;
    b>>=1;a=(a*a)%mod;
  }  
  return ans;  
}
long long f[N];
bool vis[N];
int prim[N],mu[N],sum[N];
long long C[N],g[N];
void get_mu(int n){
  mu[1]=1;
  g[1]=C[0]=C[1]=1ll;
  for(int i=2;i<=n;i++){
  	g[i]=power(f[i],mod-2);C[i]=1;
    if(!vis[i]){mu[i]=-1;prim[++prim[0]]=i;}
    for(int j=1;j<=prim[0]&&i*prim[j]<=n;j++){
      vis[i*prim[j]]=1;
      if(i%prim[j]==0)break;
      else mu[i*prim[j]]=-mu[i];
    }
  }
  for(int i=1;i<=n;++i){
    if(!mu[i])continue;
  	for(int j=i;j<=n;j+=i)
    C[j]=1ll*C[j]*(mu[i]==1?f[j/i]:g[j/i])%mod;
  }
  for(int i=2;i<=n;++i)C[i]=1ll*C[i]*C[i-1]%mod;
}
int n,m;
int main()
{
  f[1]=f[2]=1ll;
  for(int i=3;i<=N-10;i++)f[i]=f[i-1]+f[i-2],f[i]%=mod;
  get_mu(N-10);
  int T=read();
  while(T--){
    n=read();m=read();
    if(n>m)swap(n,m);
    long long ans=1ll;
    for(int i=1,lim=0;i<=n;i=lim+1){
      lim=min(n/(n/i),m/(m/i));
      ans=1ll*ans*power(C[lim]*power(C[i-1],mod-2),1ll*(n/i)*(m/i)%(mod-1));
      ans%=mod;
    }
    printf("%lld\n",ans);
  }
  return 0;
}

P3327 [SDOI2015]约数个数和

$\sum_{i=1}^n\sum_{j=1}^m\sum_{k|gcd(i,j)}1$

反演过程：

$F(x)=\sum_{i|x}1$

$\sum_{i=1}^n\sum_{j=1}^mF(gcd(i,j))$

$\sum_{d=1}^{min(n,m)}\sum_{i=1}^n\sum_{j=1}^mF(d)[gcd(i,j)=d]$

$\sum_{d=1}^{min(n,m)}F(d)\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=d]$

$\sum_{d=1}^{min(n,m)}F(d)\sum_{d’=1}^{\left\lfloor\frac{min(n,m)}{d}\right\rfloor}\mu(d’)\left\lfloor\frac{n}{d’d}\right\rfloor\left\lfloor\frac{m}{d’d}\right\rfloor$

$\sum_{T=1}^{min(n,m)}\sum_{d|T}F(d)\mu\left(\frac{T}{d}\right){\left\lfloor\frac{n}{T}\right\rfloor}{\left\lfloor\frac{m}{T}\right\rfloor}$

$\sum_{T=1}^{min(n,m)}{\left\lfloor\frac{n}{T}\right\rfloor}{\left\lfloor\frac{m}{T}\right\rfloor}\sum_{d|T}F(d)\mu\left(\frac{T}{d}\right)$

$f(x)=\sum_{d|T}F(d)\mu\left(\frac{T}{d}\right)$

$\sum_{T=1}^{min(n,m)}{\left\lfloor\frac{n}{T}\right\rfloor}{\left\lfloor\frac{m}{T}\right\rfloor}f(T)$

$\ \ \ \ \ \,$ $O(n\log n)$预处理$F$，$f$和$\mu$，询问分块，复杂度$O(\sqrt n\log n)$，总时间复杂度$O(n\log n+T\sqrt n\log n)$，和P3312 [SDOI2014]数表这道题差不多

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<cmath>
using namespace std;
const int inf=0x7fffffff;
const double eps=1e-10;
const double pi=acos(-1.0);
const int N=50010;
inline int read(){
  int x=0,f=1;char ch;ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
  return x*f;
}
bool vis[N];
int prim[N],mu[N],sum[N];
long long g[N];
void get_mu(int n){
  mu[1]=1;
  for(int i=2;i<=n;i++){
    if(!vis[i]){mu[i]=-1;prim[++prim[0]]=i;}
    for(int j=1;j<=prim[0]&&i*prim[j]<=n;j++){
      vis[i*prim[j]]=1;
      if(i%prim[j]==0)break;
      else mu[i*prim[j]]=-mu[i];
    }
  }
  for(int i=1;i<=n;i++)sum[i]=sum[i-1]+mu[i];
  for(int i=1;i<=n;i++){
    long long ans=0;
    for(int l=1,r;l<=i;l=r+1){
      r=(i/(i/l));
      ans+=1ll*(r-l+1)*1ll*(i/l);
    }
    g[i]=ans;
  }
}
long long Ans(int n,int m){
  int max_rep=min(n,m);
  long long ans=0;
  for(int l=1,r;l<=max_rep;l=r+1){
    r=min(n/(n/l),m/(m/l));
  	ans+=(sum[r]-sum[l-1])*1ll*g[n/l]*1ll*g[m/l];
  }
  return ans;
}
int main()
{
  int T=read();
 	get_mu(N-10);
 	while(T--){
 		int a=read(),b=read();
 		printf("%lld\n",Ans(a,b));
  }
  return 0;
}

P3455 [POI2007]ZAP-Queries

$\sum_{i=1}^a\sum_{j=1}^b[gcd(i,j)=c]$

反演过程：

$\sum_{i=1}^a\sum_{j=1}^b[gcd(i,j)=1]$

$\sum_{i=1}^{\left\lfloor\frac{a}{c}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{b}{c}\right\rfloor}ϵ(gcd(i,j))$

$\sum_{i=1}^{\left\lfloor\frac{a}{c}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{b}{c}\right\rfloor}(\mu*1)(gcd(i,j))$

$\sum_{i=1}^{\left\lfloor\frac{a}{c}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{b}{c}\right\rfloor}\sum_{d|gcd(i,j)}\mu(d)\times 1$

$\sum_{x=1}^{\left\lfloor\frac{min(a,b)}{c}\right\rfloor}\sum_{d|x}\mu(d){\left\lfloor\frac{a}{xc}\right\rfloor}{\left\lfloor\frac{b}{xc}\right\rfloor}$

$\sum_{d=1}^{\left\lfloor\frac{min(a,b)}{c}\right\rfloor}\mu(d){\left\lfloor\frac{a}{dc}\right\rfloor}{\left\lfloor\frac{b}{dc}\right\rfloor}$

$\ \ \ \ \ \,$ 裸题啊！模板啊！$O(n)$预处理$\mu$，询问分块，复杂度$O(\sqrt n)$，总时间复杂度$O(n+T\sqrt n)$

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<cmath>
using namespace std;
const int inf=0x7fffffff;
const double eps=1e-10;
const double pi=acos(-1.0);
const int N=50010;
inline int read(){
  int x=0,f=1;char ch;ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
  return x*f;
}
bool vis[N];
int prim[N],mu[N],sum[N],k;
void get_mu(int n){
  mu[1]=1;
  for(int i=2;i<=n;i++){
    if(!vis[i]){mu[i]=-1;prim[++prim[0]]=i;}
    for(int j=1;j<=prim[0]&&i*prim[j]<=n;j++){
      vis[i*prim[j]]=1;
      if(i%prim[j]==0)break;
      else mu[i*prim[j]]=-mu[i];
    }
  }
  for(int i=1;i<=n;i++)
  sum[i]=sum[i-1]+mu[i];
}
long long Ans(int a,int b){
  int max_rep=min(a,b);
  long long ans=0;
  for(int l=1,r;l<=max_rep;l=r+1){
    r=min(a/(a/l),b/(b/l));
    ans+=(long long)(a/(l*k))*(long long)(b/(l*k))*(long long)(sum[r]-sum[l-1]);
  }
  return ans;
}
int T;
int main()
{
 	T=read();
 	get_mu(N-10);
 	while(T--){
 		int a=read(),b=read();k=read();
 		printf("%lld\n",Ans(a,b));
  }
  return 0;
}

P1829 [国家集训队]Crash的数字表格 / JZPTAB

$\sum_{i=1}^n\sum_{j=1}^m lca(i,j)$

反演过程：

$\sum_{i=1}^n\sum_{j=1}^m\frac{ij}{gcd(i,j)}$

$\sum_{d=1}^{min(n,m)}\sum_{i=1}^n\sum_{j=1}^m\frac{ij}{d}[gcd(i,j)=d]$

$\sum_{d=1}^{min(n,m)}\frac{1}{d}\sum_{i=1}^n\sum_{j=1}^mij[gcd(i,j)=d]$

$\sum_{d=1}^{min(n,m)}\frac{1}{d}\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}ij\cdot d^2[gcd(i,j)=1]$

$\sum_{d=1}^{min(n,m)}d\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}ij[gcd(i,j)=1]$

$\sum_{d=1}^{min(n,m)}d\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}ijϵ(gcd(i,j))$

$\sum_{d=1}^{min(n,m)}d\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}ij\sum_{k|gcd(i,j)}\mu(k)$

$\sum_{d=1}^{min(n,m)}d\sum_{k=1}^{\left\lfloor\frac{min(n,m)}{d}\right\rfloor}\mu(k)\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}ij[k|gcd(i,j)]$

$\sum_{d=1}^{min(n,m)}d\sum_{k=1}^{\left\lfloor\frac{min(n,m)}{d}\right\rfloor}\mu(k)\sum_{i=1}^{\left\lfloor\frac{n}{dk}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{dk}\right\rfloor}ij\cdot k^2$

$\sum_{d=1}^{min(n,m)}d\sum_{k=1}^{\left\lfloor\frac{min(n,m)}{d}\right\rfloor}\mu(k)\cdot k^2\sum_{i=1}^{\left\lfloor\frac{n}{dk}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{dk}\right\rfloor}ij$

$\begin{aligned}F(n,m)=&\sum_{k=1}^{\frac{min(n,m)}{d}}\mu(k)\cdot k^2\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}ij\\=&\sum_{k=1}^{\frac{min(n,m)}{d}}\mu(k)\cdot k^2\cdot\frac{\left\lfloor\frac{n}{k}\right\rfloor\cdot(\left\lfloor\frac{n}{k}\right\rfloor+1)}{2}\times\frac{\left\lfloor\frac{m}{k}\right\rfloor\cdot(\left\lfloor\frac{m}{k}\right\rfloor+1)}{2} \end{aligned}$

$\sum_{d=1}^{min(n,m)}d\times F\left(\left\lfloor\frac{n}{k}\right\rfloor,\left\lfloor\frac{m}{k}\right\rfloor\right)$

$\ \ \ \ \ \,$ 感觉很神奇，需要连续提取 $2$ 次公约数，$O(n)$预处理$\mu$，分块询问$F$,$O(\sqrt{\sqrt n})$,答案询问分块，复杂度$O(\sqrt n)$，嵌套起来总时间复杂度$O(n+n^{\frac{3}{4}})$，代码比较丑

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<cmath>
using namespace std;
const int inf=0x7fffffff;
const double eps=1e-10;
const double pi=acos(-1.0);
inline int read(){
    int x=0,f=1;char ch;ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int N=10010000;
const long long mod=20101009;
long long sum[N];
bool vis[N];
int prim[N],mu[N];
void get_mu(int n){
  mu[1]=1;
  for(int i=2;i<=n;i++){
    if(!vis[i]){mu[i]=-1;prim[++prim[0]]=i;}
    for(int j=1;j<=prim[0]&&i*prim[j]<=n;j++){
      vis[i*prim[j]]=1;
      if(i%prim[j]==0)break;
      else mu[i*prim[j]]=-mu[i];
    }
  }
  for(int i=1;i<=n;i++)
  sum[i]=(sum[i-1]+1ll*mu[i]*1ll*i%mod*1ll*i%mod)%mod;
}
int main()
{
 	int n=read(),m=read();
 	if(n>m)swap(n,m);
  get_mu(n);
  long long ans=0;
  long long inv2=(mod+1ll)/2ll;
  for(int d=1;d<=n;d++){
    int x=n/d,y=m/d,minn=min(x,y);
    long long Sum=0ll;
    for(int l=1,r;l<=minn;l=r+1ll){
    	r=min(x/(x/l),y/(y/l));
      Sum=(Sum+(sum[r]-sum[l-1])%mod*(((1ll+x/l)%mod*1ll*(x/l)%mod*inv2%mod)%mod)%mod*(((1ll+y/l)%mod*1ll*(y/l)%mod*inv2%mod)%mod)%mod)%mod;
    }
    ans=(ans+Sum*1ll*d)%mod;
  }
 	printf("%lld\n",(ans%mod+mod)%mod);
  return 0;
}

扩展：这个题其实是两道题的融合，上面的方法是过不了JZPTAB的，在bzoj上面是权限题，所以先挖坑，我们下面继续来化简：

$\sum_{d=1}^{min(n,m)}d\sum_{k=1}^{\left\lfloor\frac{min(n,m)}{d}\right\rfloor}\mu(k)\cdot k^2\sum_{i=1}^{\left\lfloor\frac{n}{dk}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{dk}\right\rfloor}ij$

$\sum_{d=1}^{min(n,m)}\sum_{k=1}^{\left\lfloor\frac{min(n,m)}{d}\right\rfloor}d\cdot \mu(k)\cdot k^2\sum_{i=1}^{\left\lfloor\frac{n}{dk}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{dk}\right\rfloor}ij$

$\sum_{T=1}^{min(n,m)}\sum_{i=1}^{\left\lfloor\frac{n}{T}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{T}\right\rfloor}ij\sum_{d|T}\frac{T}{d}\cdot \mu(d)\cdot d^2$

$\sum_{T=1}^{min(n,m)}\sum_{i=1}^{\left\lfloor\frac{n}{T}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{T}\right\rfloor}ij\sum_{d|T}T \mu(d) d$

$F(T)=\sum_{d|T}T \mu(d) d$

$\sum_{T=1}^{min(n,m)}\frac{\left\lfloor\frac{n}{T}\right\rfloor\cdot(\left\lfloor\frac{n}{T}\right\rfloor+1)}{2}\times\frac{\left\lfloor\frac{m}{T}\right\rfloor\cdot(\left\lfloor\frac{m}{T}\right\rfloor+1)}{2}\times F(T)$

$\ \ \ \ \ \,$ 显然，$F$是积性函数，我们最快可以$O(n)$地把他筛出来，具体操作可以看【积性函数的线性筛】，欧拉筛三步走，询问分块，复杂度$O(\sqrt n)$,总时间复杂度$O(n+T\sqrt n)$

$\tt step1$. 如果$p$是素数：
$f(p)=p-p^2$

$\tt step2$. 如果$p$是素数，$i\%p\neq0$：$f(pi)=f(i)\times (p-p^2)$

$\tt step3$. 如果$p$是素数，$i\%p=0$：我们把 $pi$ 分解成 $p^cx$ ：
$f(pi)=f(p^cx)=f(x)\times(p^c-p^{c+1})$

代码

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<vector>
#include<string>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<set>
using namespace std;
const int inf=0x7fffffff;
const double eps=1e-10;
const double pi=acos(-1.0);
//char buf[1<<15],*S=buf,*T=buf;
//char getch(){return S==T&&(T=(S=buf)+fread(buf,1,1<<15,stdin),S==T)?0:*S++;}
inline int read(){
	int x=0,f=1;char ch;ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=0;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch&15);ch=getchar();}
	if(f)return x;else return -x;
}
const int N=1e7+10;
const long long mod=20101009;
long long inv2=(mod+1ll)/2ll;
bool vis[N];
long long pri[N],cnt[N],power[N];
long long prime[N],f[N];
void Get_Shai(long long n){
  f[1]=1;
  for(long long i=1;i<=n;i++)power[i]=1;
  for(long long i=2;i<=n;i++){
    if(!vis[i]){
      cnt[i]=1;pri[i]=i;power[i]=i;
      prime[++prime[0]]=i;
      f[i]=(1ll*i-1ll*i*i%mod+mod)%mod;
    }
    for(long long j=1,v,pc;j<=prime[0]&&i*prime[j]<=n;j++){
      v=i*prime[j];
      vis[v]=1;
      if(i%prime[j]==0){
        cnt[v]=cnt[i]+1;pri[v]=pri[i];power[v]=(1ll*power[i]*pri[i])%mod;
        f[v]=f[v/power[v]]*(1ll*power[v]-1ll*power[v]*pri[i]%mod+mod)%mod;
        break;
      }
      cnt[v]=1;pri[v]=prime[j];power[v]=prime[j];
      f[v]=(f[i]*f[prime[j]])%mod;
    }
  }
  for(int i=1;i<=n;i++)f[i]=(1ll*f[i]+f[i-1])%mod;
}
long long Get_ans(int x,int y){
  long long Sum=0;
  for(int l=1,r;l<=x;l=r+1){
    r=min(x/(x/l),y/(y/l));
    Sum=(Sum+(1ll*f[r]-f[l-1]+mod)%mod*(((1ll+x/l)%mod*1ll*(x/l)%mod*inv2%mod)%mod)%mod*(((1ll+y/l)%mod*1ll*(y/l)%mod*inv2%mod)%mod)%mod)%mod;
  }
  return Sum;
}
int main()
{
	int n=read(),m=read();
	if(n>m)swap(n,m);
  Get_Shai(1ll*n);
  printf("%lld\n",(Get_ans(n,m)%mod+mod)%mod);
	return 0;
}

再扩展，这道题还可以用杜教筛加速的，具体戳这里，感觉和这道题差不多P3768，就不贴了。

P3768 简单的数学题

$\sum_{i=1}^n\sum_{j=1}^nijgcd(i,j)$

反演过程：

$\sum_{d=1}^{n}\sum_{i=1}^n\sum_{j=1}^nijd[gcd(i,j)=d]$

$\sum_{d=1}^{n}d\sum_{i=1}^n\sum_{j=1}^nij[gcd(i,j)=d]$

$\sum_{d=1}^{n}{d}\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}ij\cdot d^2[gcd(i,j)=1]$

$\sum_{d=1}^{n}{d^3}\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}ij[gcd(i,j)=1]$

$\sum_{d=1}^{n}d^3\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}ijϵ(gcd(i,j))$

$\sum_{d=1}^{n}d^3\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}ij\sum_{k|gcd(i,j)}\mu(k)$

$\sum_{d=1}^{n}d^3\sum_{k=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu(k)\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}ij[k|gcd(i,j)]$

$\sum_{d=1}^{n}d^3\sum_{k=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu(k)\sum_{i=1}^{\left\lfloor\frac{n}{dk}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{dk}\right\rfloor}ij\cdot k^2$

$\sum_{d=1}^{n}d^3\sum_{k=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu(k)\cdot k^2\sum_{i=1}^{\left\lfloor\frac{n}{dk}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{dk}\right\rfloor}ij$

$\sum_{T=1}^{n}\sum_{i=1}^{\left\lfloor\frac{n}{T}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{T}\right\rfloor}ij\sum_{d|T}d^3\cdot \mu\left(\frac{T}{d}\right)\cdot \left(\frac{T}{d}\right)^2$

$\sum_{T=1}^{n}\sum_{i=1}^{\left\lfloor\frac{n}{T}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{T}\right\rfloor}ij\sum_{d|T}T^2\cdot d\cdot \mu\left(\frac{T}{d}\right)$

$\sum_{T=1}^{n}\sum_{i=1}^{\left\lfloor\frac{n}{T}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{T}\right\rfloor}ijT^2\sum_{d|T}d\cdot \mu\left(\frac{T}{d}\right)$

$\sum_{T=1}^{n}\sum_{i=1}^{\left\lfloor\frac{n}{T}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{T}\right\rfloor}ijT^2(id*\mu)(T)$

$\sum_{T=1}^{n}\sum_{i=1}^{\left\lfloor\frac{n}{T}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{T}\right\rfloor}ijT^2\varphi(T)$

$\sum_{T=1}^{n}\frac{\left\lfloor\frac{n}{T}\right\rfloor\cdot(\left\lfloor\frac{n}{T}\right\rfloor+1)}{2}\times\frac{\left\lfloor\frac{m}{T}\right\rfloor\cdot(\left\lfloor\frac{m}{T}\right\rfloor+1)}{2}\times T^2\varphi(T)$

$\ \ \ \ \ \,$ 需要连续提取 $2$ 次公约数，和P1829有异曲同工之妙，杜教筛筛出 $T^2\varphi(T)$ 的前缀和，分块询问答案询问，总时间复杂度$O(n^{\frac{2}{3}})$，杜教筛详见【莫比乌斯反演和杜教筛】

$f(x)=x^2\varphi(x)$

$g(x)=x^2\ \ \ ,\sum_{i=1}^{x}g(i)=\frac{x(x+1)(2x+1)}{6}$

$(fg)(x)=x^3\ \ \ ,\sum_{i=1}^{x}(fg)(i)=\frac{x^2(x+1)^2}{4}$

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<map>
#include<stack>
using namespace std;
inline long long read(){
  long long x=0,f=1;char ch;ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-') f=0;ch=getchar();}
  while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch&15);ch=getchar();}
  if(f)return x;else return -x;
}
const int N=8000010;
long long mod,n,inv6,inv4;
int prim[N];
long long f[N];
bool vis[N];
void get_f(int n){
  f[1]=1;
  for(int i=2;i<=n;i++){
    if(!vis[i]){f[i]=i-1;prim[++prim[0]]=i;}
    for(int j=1;j<=prim[0]&&i*prim[j]<=n;j++){
      vis[i*prim[j]]=1;
      if(i%prim[j]==0){f[i*prim[j]]=f[i]*prim[j];break;}
      else f[i*prim[j]]=f[i]*(prim[j]-1);
    }
  }
  for(int i=1;i<=n;++i)f[i]=(f[i-1]+1ll*f[i]*i%mod*i%mod)%mod;
}
map<long long,long long> mp;
long long power(long long a,long long b){
  long long ans=1;
  while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}
  return ans;
}
long long Sumfg(long long x){x%=mod;return x*(x+1)%mod*x%mod*(x+1)%mod*inv4%mod;}
long long Sumg(long long x){x%=mod;return x*(x+1)%mod*(x+x+1)%mod*inv6%mod;}
long long Sumf(long long x){
  if(x<=min(N-10,(int)n))return f[x];
  if(mp[x])return mp[x];
  long long ret=Sumfg(x);
  for(long long i=2,j;i<=x;i=j+1){
  	j=x/(x/i);
  	ret=(ret-(Sumg(j)-Sumg(i-1)+mod)%mod*Sumf(x/i)%mod+mod)%mod;
  }
  return mp[x]=(ret+mod)%mod;
}
int main()
{
  mod=read();n=read();
  inv4=power(4,mod-2);
  inv6=power(6,mod-2);
  get_f(min(N-10,(int)n));
  long long ans=0;
  for(long long i=1,j;i<=n;i=j+1){
    j=n/(n/i);
    ans=(ans+(Sumf(j)-Sumf(i-1))%mod*Sumfg(n/i)%mod)%mod;
  }
  printf("%lld\n",(ans+mod)%mod);
  return 0;
}

P4240 毒瘤之神的考验

$\sum_{i=1}^n\sum_{j=1}^m\varphi(ij)$

反演过程：

$\sum_{i=1}^n\sum_{j=1}^m\frac{\varphi(i)\varphi(j)gcd(i,j)}{\varphi(gcd(i,j))}$

$\sum_{d=1}^{min(n,m)}\sum_{i=1}^n\sum_{j=1}^m\frac{\varphi(i)\varphi(j)d}{\varphi(d)}[gcd(i,j)=d]$

$\sum_{d=1}^{min(n,m)}\frac{d}{\varphi(d)}\sum_{i=1}^n\sum_{j=1}^m\varphi(i)\varphi(j)[gcd(i,j)=d]$

$\sum_{d=1}^{min(n,m)}\frac{d}{\varphi(d)}\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}\varphi(di)\varphi(dj)[gcd(i,j)=1]$

$\sum_{d=1}^{min(n,m)}\frac{d}{\varphi(d)}\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}\varphi(di)\varphi(dj)ϵ(gcd(i,j))$

$\sum_{d=1}^{min(n,m)}\frac{d}{\varphi(d)}\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}\varphi(di)\varphi(dj)\sum_{k|gcd(i,j)}\mu(k)$

$\sum_{d=1}^{min(n,m)}\frac{d}{\varphi(d)}\sum_{k=1}^{\left\lfloor\frac{min(n,m)}{dk}\right\rfloor}\mu(k)\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}\varphi(di)\varphi(dj)[k|gcd(i,j)]$

$\sum_{d=1}^{min(n,m)}\frac{d}{\varphi(d)}\sum_{k=1}^{\left\lfloor\frac{min(n,m)}{dk}\right\rfloor}\mu(k)\sum_{i=1}^{\left\lfloor\frac{n}{dk}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{dk}\right\rfloor}\varphi(dik)\varphi(djk)$

$\sum_{T=1}^{min(n,m)}\sum_{i=1}^{\left\lfloor\frac{n}{T}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{T}\right\rfloor}\varphi(iT)\varphi(jT)\sum_{d|T}\frac{d}{\varphi(d)}\mu(\frac{T}{d})$

$\ \ \ \ \ \,$ $O(n)$预处理出$\mu$,$\varphi$，$O(n\log n)$预处理出后面的$\sum_{d|T}\frac{d}{\varphi(d)}\mu(\frac{T}{d})$，然后对前面的进行分块操作，会发现要存很多东西，于是我们一边分块，一边操作，总复杂度很玄学，大约是$O(n\log n+nT^{\frac{2}{3}}+T(\sqrt n+\left\lfloor\frac{n}{T^{\frac{1}{3}}}\right\rfloor))$,能过就行了XD,~~(代码加了信仰fread)~~

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<cctype>
#include<vector>
using namespace std;
const int inf=0x7fffffff;
const double eps=1e-10;
const double pi=acos(-1.0);
char buf[1<<15],*S=buf,*TT=buf;
char getch(){return S==TT&&(TT=(S=buf)+fread(buf,1,1<<15,stdin),S==TT)?0:*S++;}
inline int read(){
  int x=0,f=1;char ch;ch=getch();
  while(ch<'0'||ch>'9'){if(ch=='-') f=0;ch=getch();}
  while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch&15);ch=getch();}
  if(f)return x;else return -x;
}
const int N=100010;
const int mod=998244353;
const int B=35;
bool vis[N];
int prim[N],phi[N],mu[N],inv[N];
int F[N];
vector<int> G[N],T[B+1][B+1];
void get_phi_mu_inv(int n){
  phi[1]=mu[1]=inv[1]=1;
  for(int i=2;i<=n;i++){
    if(!vis[i])phi[i]=i-1,mu[i]=-1,prim[++prim[0]]=i;
    for(int j=1;j<=prim[0]&&i*prim[j]<=n;j++){
      vis[i*prim[j]]=1;
      if(i%prim[j]==0){phi[i*prim[j]]=phi[i]*prim[j];break;}
      else phi[i*prim[j]]=phi[i]*(prim[j]-1),mu[i*prim[j]]=-mu[i];
    }
    inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
  }
}
void init(int n){
  for(int i=1;i<=n;i++)
  for(int j=i;j<=n;j+=i)
  F[j]=(F[j]+(1ll*mu[j/i]*i*inv[phi[i]]%mod+mod)%mod)%mod;
  for(int i=1;i<=n;i++){
    G[i].push_back(0);
    for(int j=1;j<=n/i;j++)
    G[i].push_back((G[i][j-1]+phi[i*j])%mod);
  }
  for(int j=1;j<=B;j++)
    for(int k=j;k<=B;k++){
    int len=n/max(j,k);
    T[j][k].push_back(0);
    for(int i=1;i<=len;i++)
    T[j][k].push_back((T[j][k][i-1]+1ll*F[i]*G[i][j]%mod*G[i][k]%mod)%mod);
  }
}
long long Solve(int n,int m){
  long long res=0;
  int ed=m/B;
  for(int i=1;i<=ed;i++)
  res=(res+1ll*F[i]*G[i][n/i]%mod*G[i][m/i]%mod)%mod;
  for(int l=m/B+1,r,ln,lm;l<=n;l=r+1){
  	ln=n/l,lm=m/l;
    r=min(n/ln,m/lm);
    res=(res+(T[ln][lm][r]-T[ln][lm][l-1]+mod)%mod)%mod;
  }
  return res;
}
int main()
{
  get_phi_mu_inv(100000);init(100000);
  int t=read();
  while(t--){
    int n=read(),m=read();if(n>m)swap(n,m);
    printf("%lld\n",Solve(n,m));
  }
  return 0;
}

P1587 [NOI2016]循环之美

$\ \ \ \ \ \,$对于一个$K$进制下的无限循环小数，在最简形态下，分母一定和$K$互质，所以这道题，就是求:
$\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=1][gcd(j,K)=1]$

反演过程：

$\sum_{j=1}^m[gcd(j,K)=1]\sum_{i=1}^n[gcd(i,j)=1]$

$\sum_{j=1}^m[gcd(j,K)=1]\sum_{i=1}^nϵ(gcd(i,j))$

$\sum_{j=1}^m[gcd(j,K)=1]\sum_{i=1}^n\sum_{k|gcd(i,j)}\mu(k)$

$\sum_{k=1}^{min(n,m)}\mu(k)\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}[gcd(jk,K)=1]$

$\sum_{k=1}^{min(n,m)}\mu(k)[gcd(k,K)=1]\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}[gcd(j,K)=1]$

$\sum_{k=1}^{min(n,m)}\mu(k)[gcd(k,K)=1]\sum_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}[gcd(j,K)=1]\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}$

$\sum_{k=1}^{min(n,m)}\mu(k)[gcd(k,K)=1]\sum_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}[gcd(j,K)=1]{\left\lfloor\frac{n}{k}\right\rfloor}$

$f(x,K)=\sum_{i=1}^{x}\mu(i)[gcd(i,K)=1]$

$s(x)=\sum_{i=1}^{x}[gcd(i,K)=1]$

$\sum_{k=1}^{min(n,m)}\mu(k)[gcd(k,K)=1]{\left\lfloor\frac{n}{k}\right\rfloor}s\left(\left\lfloor\frac{m}{k}\right\rfloor\right)$

$\ \ \ \ \ \,$然而还没有完，我们求出$f$和$s$，也就是方便分块操作，现在我们得化简它们:

$s(x)$
$s(x)=\sum_{i=1}^{x}[gcd(i,K)=1]$
因为若是 $gcd(a,K)=1$，那么就有 $gcd(a+bk,K)=1$。
所以有：
$s(x)=\left\lfloor\frac{x}{k}\right\rfloor s(k)+s(x\%k)$
所以只需要暴力求出$k$以内的$s$就可以了。
$f(x,K)$

$\sum_{i=1}^{x}\mu(i)[gcd(i,K)=1]$

$\sum_{i=1}^{x}\mu(i)ϵ(gcd(i,K))$

$\sum_{i=1}^{x}\mu(i)\sum_{d|gcd(i,K)}\mu(d)$

$\sum_{d=1}^{min(x,K)}\mu(d)\sum_{i=1}^x\mu(i)[d|gcd(i,K)]$

$\sum_{d=1}^{min(x,K)}\mu(d)\sum_{i=1}^{\left\lfloor\frac{x}{d}\right\rfloor}\mu(id)[d|gcd(id,K)]$

$\sum_{d=1}^{min(x,K)}\mu(d)\sum_{i=1}^{\left\lfloor\frac{x}{d}\right\rfloor}\mu(id)[d|K]$

$\sum_{d|K}\mu(d)\sum_{i=1}^{\left\lfloor\frac{x}{d}\right\rfloor}\mu(id)$

$\sum_{d|K}\mu(d)\sum_{i=1,gcd(i,d)=1}^{\left\lfloor\frac{x}{d}\right\rfloor}\mu(d)\mu(i)$

$\sum_{d|K}\mu(d)^2\sum_{i=1,gcd(i,d)=1}^{\left\lfloor\frac{x}{d}\right\rfloor}\mu(i)$

$\sum_{d|K}\mu(d)^2\sum_{i=1}^{\left\lfloor\frac{x}{d}\right\rfloor}\mu(i)[gcd(i,d)=1]$

$\sum_{d|K}\mu(d)^2f\left({\left\lfloor\frac{x}{d}\right\rfloor},d\right)$

这个怎么办啊？每次递归求解，但是当$K=1$的时候，就没有办法了，我们试一试化一下$K=1$的情况:

$\sum_{i=1}^{x}\mu(i)[gcd(i,1)=1]$

$\sum_{i=1}^{x}\mu(i)$

一个杜教筛就完了。

复杂度大概是$O(n^{\frac{2}{3}})$
感觉题目还是比较难的，反正我一开始是没有想出来，翻了题解，主要是对于$s$的处理，有多加一维描述，还有递归处理，程序的最终复杂度呢，大概就在$O(n^{\frac{2}{3}})$的样子

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<cctype>
using namespace std;
const int inf=0x7fffffff;
const double eps=1e-10;
const double pi=acos(-1.0);
//char buf[1<<15],*S=buf,*T=buf;
//char getch(){return S==T&&(T=(S=buf)+fread(buf,1,1<<15,stdin),S==T)?0:*S++;}
inline int read(){
  int x=0,f=1;char ch;ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-') f=0;ch=getchar();}
  while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch&15);ch=getchar();}
  if(f)return x;else return -x;
}
const int N=10000010;
int n,K,m;
int pr[2010];
bool vis[N];
int prim[N],mu[N],Sum_mu[N];
map<pair<int,int>,int> used;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
void init(){
  for(int i=1;i<=K;i++)pr[i]=pr[i-1]+(gcd(i,K)==1);
  mu[1]=1;
  for(int i=2;i<N;i++){
    if(!vis[i]){mu[i]=-1;prim[++prim[0]]=i;}
    for(int j=1;j<=prim[0];j++){
      if(i*prim[j]>=N) break;
      vis[i*prim[j]]=1;
      if(i%prim[j]==0){mu[i*prim[j]]=0;break;}
      mu[i*prim[j]]=-mu[i];
    }
  }
  for(int i=1;i<N;i++)Sum_mu[i]=Sum_mu[i-1]+mu[i];
}
int s(int x){return pr[x%K]+1ll*(x/K)*pr[K];}
int f(int x,int k){
  if(!k||!x)return 0;
  if(k==1&&x<N)return Sum_mu[x];
  if(used[make_pair(x,k)])return used[make_pair(x,k)];
  if(k==1){
  	int ret=1;
    for(int l=2,r;l<=x;l=r+1)
    r=x/(x/l),ret-=(r-l+1)*f(x/l,1);
  	return used[make_pair(x,k)]=ret;
  }
  int ret=0;
  for(int i=1;i*i<=k;i++)if(k%i==0){
    if(mu[i])ret+=f(x/i,i);
    if(i*i!=k&&mu[k/i])
    ret+=f(x/(k/i),k/i);
  }
  return used[make_pair(x,k)]=ret;
}
int main()
{
  n=read();m=read();K=read();
  init();
  long long ans=0;
  for(int l=1,r;l<=min(n,m);l=r+1){
    r=min(n/(n/l),m/(m/l));
    ans+=1ll*(f(r,K)-f(l-1,K))*(n/l)*s(m/l);
  }
  printf("%lld\n",ans);
  return 0;
}