那这题的证明bigmurmur大佬已经写得很清楚了
我就提供一个我常数比较大但是比较简单于是用了map瞎记忆化卡常的代码吧
#include<bits/stdc++.h>
using namespace std;
const int N=2e6;
int cnt;
int pri[N/10],mu[N+50],low[N+50],summ[N+50];
bool isp[N+50];
void init() {
isp[1]=1,low[1]=mu[1]=1;
for(int i=2;i<=N;++i) {
if(!isp[i]) pri[++cnt]=low[i]=i,mu[i]=-1;
for(int j=1;j<=cnt&&pri[j]*i<=N;++j) {
isp[i*pri[j]]=1;
if(!(i%pri[j])) {
low[pri[j]*i]=pri[j]*low[i];
if(low[i]==i) mu[pri[j]*i]=0;
else mu[pri[j]*i]=mu[pri[j]*low[i]]*mu[i/low[i]];
break;
}
low[pri[j]*i]=pri[j];
mu[pri[j]*i]=mu[pri[j]]*mu[i];
}
}
for(int i=1;i<=N;++i) summ[i]=summ[i-1]+mu[i];
}
map<int,int> mm;
map<int,map<int,map<int,long long> > > mp;
int sm(int n) {
if(n<=N) return summ[n];
if(mm[n]) return mm[n];
int ans=0,tmp;
for(int l=2,r;l<=n;l=r+1) {
tmp=n/l;
r=n/tmp;
ans+=(r-l+1)*sm(tmp);
}
return mm[n]=1-ans;
}
int mmu(int x) {
if(x<=N) return mu[x];
}
long long g(int n,int m,int k) {
if(n==0||m==0) return 0;
if(mp[n][m][k]) return mp[n][m][k];
long long ans=0;
if(k==1) {
if(n>m) swap(n,m);
for(int l=1,r;l<=n;l=r+1) {
int tmp1=n/l,tmp2=m/l;
r=min(n/tmp1,m/tmp2);
ans+=1ll*(sm(r)-sm(l-1))*tmp1*tmp2;
}
return mp[n][m][k]=ans;
}
int srt=sqrt(k);
for(int i=1;i<=srt;++i)
if(!(k%i)) ans+=1ll*mmu(i)*g(m/i,n,i)+1ll*mmu(k/i)*g(m/(k/i),n,k/i)*(i!=k/i);
return mp[n][m][k]=ans;
}
int n,m,k;
int main() {
init();
scanf("%d%d%d",&n,&m,&k);
printf("%lld\n",g(n,m,k));
return 0;
}