分析
可以发现，$k$ 进制分数 $\frac{x}{y}$ 是纯循环的当且仅当 $\gcd(y,k)=1$。证明可以点这里。
另外为了避免算重，我们只统计最简分数。
那么我们要求的东西就是（设 $l=\min(n,m)$）
$$
\begin{aligned}
&\sum_{x=1}^n\sum_{y=1}^m[\gcd(x,y)=1][\gcd(y,k)=1]\\
=&\sum_{x=1}^n\sum_{y=1}^m\sum_{d|x,d|y}\mu(d)[\gcd(y,k)=1]\\
=&\sum_{d=1}^l\mu(d)\left\lfloor\frac{n}{d}\right\rfloor\sum_{d|y}^m[\gcd(y,k)=1]\\
=&\sum_{d=1}^l\mu(d)\left\lfloor\frac{n}{d}\right\rfloor\sum_{y=1}^{m/d}[\gcd(dy,k)=1]\\
=&\sum_{d=1}^l[\gcd(d,k)=1]\mu(d)\left\lfloor\frac{n}{d}\right\rfloor\sum_{y=1}^{m/d}[\gcd(y,k)=1]
\end{aligned}
$$
可以数论分块，则我们需要计算两个前缀和
$$
\begin{aligned}
f(n)&=\sum_{i=1}^n[\gcd(i,k)=1]\\
g(n,k)&=\sum_{i=1}^n[\gcd(i,k)=1]\mu(i)
\end{aligned}
$$
这里为什么是 $g(n,k)$ 而不是 $g(n)$ 呢？这里先埋一个伏笔，看到后面自然就知道了（
首先考虑计算 $f(n)$。可以发现如果 $\gcd(i,k)=1$ 则 $\gcd(i+k,k)=1$，如果 $\gcd(i,k)\neq 1$ 则 $\gcd(i+k,k)\neq 1$。所以有
$$
f(n)=\left\lfloor\frac{n}{k}\right\rfloor f(k)+f(n\bmod k)
$$
因为 $k\leq 2000$，所以直接预处理出 $f(0\sim k)$ 的值即可。
再考虑算 $g(n,k)$，有
$$
\begin{aligned}
g(n,k)&=\sum_{i=1}^n\mu(i)\sum_{d|i,d|k}\mu(d)\\
&=\sum_{d|k}\mu(d)\sum_{d|i}^n\mu(i)\\
&=\sum_{d|k}\mu(d)\sum_{i=1}^{n/d}\mu(id)\\
&=\sum_{d|k}\mu(d)\sum_{i=1}^{n/d}[\gcd(i,d)=1]\mu(i)\mu(d)\\
&=\sum_{d|k}\mu(d)^2\sum_{i=1}^{n/d}[\gcd(i,d)=1]\mu(i)\\
&=\sum_{d|k}\mu(d)^2g\left(\left\lfloor\frac{n}{d}\right\rfloor,d\right)
\end{aligned}
$$
这样子直接枚举约数递归下去算即可；当 $k=1$ 时无法继续往下递归，但此时相当于要求 $\mu(i)$ 的前缀和，杜教筛即可。
代码
// ====================================
// author: M_sea
// website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define mp make_pair
using namespace std;
typedef long long ll;
int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int K=2000+10,L=1000000+10;
int n,m,k;
ll f[K];
ll F(int n) { return n/k*f[k]+f[n%k]; }
int p[L],v[L],mu[L],smu[L],cnt;
map<pair<int,int>,ll> M;
void sieve(int n) {
mu[1]=1;
for (int i=2;i<=n;++i) {
if (!v[i]) p[++cnt]=i,mu[i]=-1;
for (int j=1;j<=cnt&&i*p[j]<=n;++j) {
v[i*p[j]]=1;
if (i%p[j]) mu[i*p[j]]=-mu[i];
else break;
}
}
for (int i=1;i<=n;++i) smu[i]=smu[i-1]+mu[i];
}
ll G(int n,int k) {
if (!n) return 0;
if (k==1&&n<L) return smu[n];
if (M.count(mp(n,k))) return M[mp(n,k)];
if (k==1) {
ll res=1;
for (int l=2,r;l<=n;l=r+1) {
r=n/(n/l);
res-=(r-l+1)*G(n/l,k);
}
return M[mp(n,k)]=res;
} else {
ll res=0;
for (int d=1;d*d<=k;++d) {
if (k%d) continue;
if (mu[d]) res+=G(n/d,d);
if (d*d!=k&&mu[k/d]) res+=G(n/(k/d),k/d);
}
return M[mp(n,k)]=res;
}
}
int main() {
sieve(L-1);
n=read(),m=read(),k=read();
for (int i=1;i<=k;++i) f[i]=f[i-1]+(__gcd(i,k)==1);
ll ans=0;
for (int l=1,r;l<=min(n,m);l=r+1) {
r=min(n/(n/l),m/(m/l));
ans+=(G(r,k)-G(l-1,k))*(n/l)*F(m/l);
}
printf("%lld\n",ans);
return 0;
}