$\Rightarrow [\frac{xk^l}{y}]=[\frac{x}{y}]$

$\Rightarrow \frac{xk^l}{y}-\lfloor\frac{xk^l}{y}\rfloor=\frac{x}{y}-\lfloor\frac{x}{y}\rfloor$

$\Rightarrow xk^l-\lfloor\frac{xk^l}{y}\rfloor*y=x-\lfloor\frac{x}{y}\rfloor*y$

$\Rightarrow xk^l\equiv x\mod y$

$\Rightarrow k^l\equiv1\mod y$

$\Rightarrow (k,y)=1$

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

## 一:考虑处理$[(i,j)=1]$

(有公式恐惧症下转法二)

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

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

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

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

$=\sum_{j=1}^m[(j,k)=1]\sum_{d|j}^n\mu(d)\frac{n}{d}$

$=\sum_{d=1}^n\mu(d)\frac{n}{d}\sum_{j=1}^m[d|j][(j,k)=1]$

$=\sum_{d=1}^n\mu(d)\frac{n}{d}\sum_{jd=1}^m[d|jd][(jd,k)=1]$

$j$用$jd$替换一下来减少限制(下同)

$=\sum_{d=1}^n\mu(d)\frac{n}{d}\sum_{j=1}^{\frac{m}{d}}[(jd,k)=1]$

$=\sum_{d=1}^n\mu(d)[(d,k)=1]\frac{n}{d}\sum_{j=1}^{\frac{m}{d}}[(j,k)=1]$

#### ①:考虑化简式子

$=\sum_{d=1}^n\mu(d)\sum_{p|(d,k)}\mu(p)$

$=\sum_{d=1}^n\mu(d)\sum_{p|d,p|k}\mu(p)$

$=\sum_{d=1}^n\sum_{p|d}\mu(d)\sum_{p|k}\mu(p)$

$=\sum_{p|k}\mu(p)\sum_{dp=1}^n\sum_{p|dp}\mu(dp)$

$=\sum_{p|k}\mu(p)\sum_{d=1}^{\frac{n}{p}}\mu(dp)$

$=\sum_{p|k}\mu(p)\sum_{d=1}^{\frac{n}{p}}\mu(dp)[(d,p)=1]$

$=\sum_{p|k}\mu(p)\sum_{d=1}^{\frac{n}{p}}\mu(d)\mu(p)[(d,p)=1]$

$=\sum_{p|k}\mu(p)^2\sum_{d=1}^{\frac{n}{p}}\mu(d)[(d,p)=1]$

$=\sum_{p|k}\mu(p)^2g(\frac{n}{p},p)$

$g(n,1)=\sum_{d=1}^n\mu(d)$直接杜教筛

#include<map>
#include<cmath>
#include<cstdio>
#include<algorithm>
#define fp(i,a,b) for(int i=a,I=b;i<=I;++i)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
using namespace std;
const int N=7e5+5,E=2e6+5;
typedef int arr[N];typedef long long ll;
struct Am{int nx,x,w;}e1[E];
struct Ans{int nx,n,m,k;ll w;}e2[E];
int n,m,k,M,c1,c2,K[2000],f1[E],f2[E];arr is,pr,mu,Smu;
int Sm(int x){
if(x<=M)return Smu[x];
int u=(x+2017)%E;
for(int i=f1[u];i;i=e1[i].nx)if(e1[i].x==x)return e1[i].w;
e1[++c1]=Am{f1[u],x,1};f1[u]=c1;
int&w=e1[c1].w,i=2,j=sqrt(x);
for(;i<=j;++i)w-=Sm(x/i);
for(;i<=x;i=j+1)j=x/(x/i),w-=(j-i+1)*Sm(x/i);
return w;
}
ll sol(int n,int m,int k){
if(!n||!m)return 0;
int u=(2017ll*n+m+k)%E;
for(int i=f2[u];i;i=e2[i].nx)if(e2[i].n==n&&e2[i].m==m&&e2[i].k==k)return e2[i].w;
e2[++c2]=Ans{f2[u],n,m,k,0};f2[u]=c2;ll&w=e2[c2].w;
if(k==1){
if(n>m)swap(n,m);
int i=1,j=sqrt(n),s,t=0,x,y;
for(;i<=j;++i,t=s)s=Sm(i),w+=1ll*(n/i)*(m/i)*(s-t);
for(;i<=n;i=j+1,t=s)x=n/i,y=m/i,j=min(n/x,m/y),s=Sm(j),w+=1ll*x*y*(s-t);
u=(2017ll*m+n+k)%E;e2[++c2]=Ans{f2[u],m,n,k,w};f2[u]=c2;
}else for(int i=1;i<=K[0]&&K[i]<=k;++i)
if(k%K[i]==0&&mu[K[i]])
w+=sol(m/K[i],n,K[i])*mu[K[i]];
return w;
}
int main(){
#ifndef ONLINE_JUDGE
file("s");
#endif
scanf("%d%d%d",&n,&m,&k);
M=min(N-5,max(k,min(n,m)));Smu[1]=mu[1]=1;
fp(i,2,M){
if(!is[i])pr[++pr[0]]=i,mu[i]=-1;
for(int j=1,x;j<=pr[0]&&(x=i*pr[j])<=M;++j){
is[x]=1;if(i%pr[j])mu[x]=-mu[i];else break;
}Smu[i]=Smu[i-1]+mu[i];
}
fp(i,1,k)if(k%i==0)K[++K[0]]=i;
printf("%lld",sol(n,m,k));
return 0;
}

#### ②:考虑分析式子

$g(n,k)=\sum_{d=1}^n\mu(d)[(d,k)=1]=\sum_{d=1}^n\mu(d)[(d,p)=1][(d,q)=1]$

$=g(n,q)-\sum_{dp=1}^n\mu(dp)[(dp,q)=1][(dp,p)=p]$

$=g(n,q)-\sum_{d=1}^{\frac{n}{p}}\mu(dp)[(d,q)=1]$

$=g(n,q)-\sum_{d=1}^{\frac{n}{p}}\mu(dp)[(d,p)=1][(d,q)=1]$

$=g(n,q)-\sum_{d=1}^{\frac{n}{p}}\mu(d)\mu(p)[(d,k)=1]$

$=g(n,q)-\mu(p)\sum_{d=1}^{\frac{n}{p}}\mu(d)[(d,k)=1]$

$=g(n,q)+g(\frac{n}{p},k)$

#include<cmath>
#include<cstdio>
#include<algorithm>
#define fp(i,a,b) for(int i=a,I=b;i<=I;++i)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
using namespace std;
const int N=1e6+5,E=2.2*N;
typedef int arr[N];
struct eg{int nx,n,k,w;}e[E];
int n,m,k,M,ce,fi[E],p[2001],q[2001];arr is,pr,mu,Smu,f;
int g(int n,int k){
if(!n||(n<=M&&k==1))return Smu[n];
int x=(1LL*n*2017+k)%E;
for(int i=fi[x];i;i=e[i].nx)if(e[i].n==n&&e[i].k==k)return e[i].w;
e[++ce]=eg{fi[x],n,k,0};fi[x]=ce;int&w=e[ce].w;
if(k==1){
w=1;int i=2,j=sqrt(n),x;
for(;i<=j;++i)w-=g(n/i,1);
for(;i<=n;i=j+1)x=n/i,j=n/x,w-=(j-i+1)*g(x,1);
}else w=g(n,q[k])+g(n/p[k],k);
return w;
}
int gcd(int a,int b){return!b?a:gcd(b,a%b);}
inline int Sf(int x){return x/k*f[k]+f[x%k];}
int main(){
#ifndef ONLINE_JUDGE
file("s");
#endif
scanf("%d%d%d",&n,&m,&k);
M=min(N-5,min(n,m));Smu[1]=mu[1]=1;
fp(i,2,M){
if(!is[i])pr[++pr[0]]=i,mu[i]=-1;
for(int j=1,x;j<=pr[0]&&(x=i*pr[j])<=M;++j){
is[x]=1;if(i%pr[j])mu[x]=-mu[i];else break;
}Smu[i]=Smu[i-1]+mu[i];
}
fp(i,1,k)f[i]=f[i-1]+(gcd(i,k)==1);
fp(i,2,k){
for(int j=2;;++j)if(i%j==0&&!is[j]){p[i]=j;break;}
for(q[i]=i;q[i]%p[i]==0;)q[i]/=p[i];
}
int i=1,j=sqrt(min(n,m)),x,y,s,t=0;long long w=0;
for(;i<=j;++i,t=s)s=g(i,k),w+=1ll*(n/i)*Sf(m/i)*(s-t);
for(;i<=min(n,m);i=j+1,t=s)x=n/i,y=m/i,j=min(n/x,m/y),
s=g(j,k),w+=1ll*x*Sf(y)*(s-t);
printf("%lld",w);
return 0;
}

## 二:考虑处理$[(j,k)=1]$

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

$=\sum_{i=1}^n\sum_{jd=1}^m[(i,jd)=1]\sum_{d|jd,d|k}\mu(d)$

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

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

$=\sum_{d|k}\mu(d)f(\frac{m}{d},n,d)$

#include<map>
#include<cmath>
#include<cstdio>
#include<algorithm>
#define fp(i,a,b) for(int i=a,I=b;i<=I;++i)
#define fd(i,a,b) for(int i=a,I=b;i>=I;--i)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
using namespace std;
const int N=1e7+5;
typedef int arr[N];
typedef long long ll;
struct da{int n,m,k;inline bool operator<(const da&b)const{return n==b.n?(m==b.m?k<b.k:m<b.m):n<b.n;}};
int n,m,k,M,K[2000];arr is,pr,mu,Smu;map<int,int>Am;map<da,ll>Ans;
int Sm(int x){
if(x<=M)return Smu[x];
if(Am[x])return Am[x];
int w=1,i=2,j=sqrt(x);
for(;i<=j;++i)w-=Sm(x/i);
for(;i<=x;i=j+1)j=x/(x/i),w-=(j-i+1)*Sm(x/i);
return Am[x]=w;
}
ll sol(int n,int m,int k){
if(!n||!m)return 0;
da now=da{n,m,k};
if(Ans[now])return Ans[now];ll w=0;
if(k==1){
if(n>m)swap(n,m);
int i=1,j=sqrt(n),s,t=0,x,y;
for(;i<=j;++i,t=s)s=Sm(i),w+=1ll*(n/i)*(m/i)*(s-t);
for(;i<=n;i=j+1,t=s)x=n/i,y=m/i,j=min(n/x,m/y),s=Sm(j),w+=1ll*x*y*(s-t);
Ans[da{m,n,k}]=w;
}else for(int i=1;i<=K[0]&&K[i]<=k;++i)
if(k%K[i]==0&&mu[K[i]])
w+=sol(m/K[i],n,K[i])*mu[K[i]];
return Ans[now]=w;
}
int main(){
#ifndef ONLINE_JUDGE
file("s");
#endif
scanf("%d%d%d",&n,&m,&k);
M=min((int)1e7,max(k,min(n,m)));mu[1]=1;
fp(i,2,M){
if(!is[i])pr[++pr[0]]=i,mu[i]=-1;
for(int j=1,x;j<=pr[0]&&(x=i*pr[j])<=M;++j){
is[x]=1;
if(i%pr[j])mu[x]=-mu[i];
else{mu[x]=0;break;}
}
}fp(i,1,M)Smu[i]=Smu[i-1]+mu[i];
fp(i,1,k)if(k%i==0)K[++K[0]]=i;
printf("%lld",sol(n,m,k));
return 0;
}