这道题我推到后面推不下去了，最后还是看了题解。还是切不了这种题唉。
前置知识：杜教筛
开始时看不出什么，我们先用经验和手玩来找一下规律。
我们考虑 \(K=10\) 的情况。根据我们的经验，如果 \(\dfrac 1y\) 是纯循环的，那么它的任意整数倍也应当是纯循环的。发现 \(y\) 可以为 \(1,3,7,9,11,13,\cdots\)。
我们不由得猜测，当且仅当 \(y\perp K\) 时，\(\dfrac 1y\) 是纯循环的。
尝试证明一下。首先证明第一个结论。如果 \(\dfrac 1y\) 是一个纯循环小数，\(\dfrac xy\) 则是这个小数乘以 \(x\) 的结果。可以将循环节的每一位乘以 \(x\) 累加到结果中。每一个循环节都是同样的结果，接受后面的进位也都相同。若进位到整数部分也不影响小数部分纯循环。
第二个结论的证明采用反证法。假设存在一个 \(y\) 使得 \(\gcd(y,K)>1\) 且 \(\dfrac 1y\) 是纯循环小数，根据第一个结论，其正整数倍数也是纯循环小数。如果 \(K\) 是 \(y\) 的倍数，显然 \(\dfrac 1y\) 是一个有限小数，矛盾。否则，设 \(z=\gcd(y,K)\)，则 \(\dfrac 1y\) 可以表示为一个有限小数 \(\dfrac 1z\) 与一个纯循环小数 \(\dfrac zy\) 的乘积。一个有限小数又可以表示为 \(\sum a_iK^i(0\le a_i<K,i<0)\) 的形式。如果一个纯循环小数乘以 \(K^k\)（\(k\) 是任意负整数），相当于在 \(K\) 进制下这个小数左移了 \(|k|\) 位，小数点后会多 \(k\) 个零。由于循环节是非零的，这样势必打破循环。乘以 \(\sum a_iK^i\) 也同理。于是这样的 \(y\) 不存在。
于是得出结论：如果没有 \(y\perp K\)，那么 \(\dfrac xy\) 不是纯循环的。第二个结论是其逆否命题，自然成立。
其实，在上面的证明过程中，\(\dfrac zy\) 仍然是一个纯循环小数。因为 \(\gcd(\dfrac yz,K)=1\)。
但是，在 \(\gcd(y,K)>1\) 时， \(\dfrac xy\) 也有可能是纯循环的。不过从第二个结论的证明过程中可以看出，若把 \(\dfrac 1y\) 表示为一个有限小数与一个纯循环小数的乘积，则 \(\dfrac xy\) 出现纯循环的情况，一定是 \(x\) 乘以那个有限小数得到了一个整数的结果。即，\(\dfrac{xz}y\) 是正整数。所以 \(\gcd(x,y)>1\)，\(\dfrac xy\) 一定不是最简的。
因此我们得出结论：一个最简分数 \(\dfrac xy\) 在 \(K\) 进制下是纯循环的，当且仅当 \(y\perp K\)。
所以题目就是要我们求：
\[\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^m[i\perp j][j\perp K]\\ =&\sum_{i=1}^n\sum_{j=1}^m\sum_{d\mid i\land d\mid j}\mu(d)[j\perp K]\\ =&\sum_{d=1}^{\min\{n,m\}}\sum_{i=1}^n\sum_{j=1}^m[d\mid i][d\mid j]\mu(d)[j\perp K]\\ =&\sum_{d=1}^{\min\{n,m\}}\mu(d)\sum_{i=1}^n[d\mid i]\sum_{j=1}^{\lfloor\frac md\rfloor}[dj\perp K]\\ =&\sum_{d=1}^{\min\{n,m\}}\lfloor\frac nd\rfloor\mu(d)[d\perp K]\sum_{j=1}^{\lfloor\frac md\rfloor}[j\perp K] \end{aligned} \]为使用数论分块，我们将这个式子除去 \(\lfloor\frac nd\rfloor\) 后拆成两个函数。
设 \(\mathbf f(n)=\sum_{i=1}^n[i\perp K]\)，即从 \(1\) 到 \(n\) 中与 \(K\) 互质的数的个数。对于一个数 \(x\)，根据欧几里得定理，\(\gcd(x,K)=\gcd(K,x\bmod K)\)，所以 \(x\perp K\iff x\bmod K\perp K\)。故 \(\mathbf f(n)=\lfloor\frac nK\rfloor\sum_{i=1}^K[i\perp K]+\mathbf f(n\bmod K)=\lfloor\frac nK\rfloor\varphi(K)+\mathbf f(n\bmod K)\)。所以最终有
\[\mathbf f(n)=\lfloor\frac nK\rfloor\mathbf f(K)+\mathbf f(n\bmod K) \]设 \(\mathbf g(n,k)=\sum_{i=1}^n\mu(i)[i\perp k]\)。
\[\begin{aligned} &\sum_{i=1}^n\mu(i)[\gcd(i,k)=1]\\ =&\sum_{i=1}^n\mu(i)\sum_{d=1}^n[d\mid i][d\mid k]\mu(d)\\ =&\sum_{d=1}^n[d\mid k]\mu(d)\sum_{i=1}^{\lfloor\frac nd\rfloor}\mu(di)\\ =&\sum_{d\mid k}\mu(d)\sum_{i=1}^{\lfloor\frac nd\rfloor}\mu(di) \end{aligned}\]好像推不下去了，我们可以想办法搞一个递推出来。
\[\begin{aligned} &\sum_{d\mid k}\mu(d)\sum_{i=1}^{\lfloor\frac nd\rfloor}[d\perp i]\mu(i)\mu(d)\\ =&\sum_{d\mid k}\mu(d)^2\mathbf g(\lfloor\frac nd\rfloor,d) \end{aligned}\]即 \(\mathbf g(n,k)=\sum_{d\mid k}\mu(d)^2\mathbf g(\lfloor\frac nd\rfloor,d)=\sum_{d\mid k}[\mu(d)\ne 0]\mathbf g(\lfloor\frac nd\rfloor,d)\)。
边界：\(\mathbf g(0,k)=0,\mathbf g(n,1)=\sum_{i=1}^n\mu(i)\)。后一个可以使用杜教筛。
于是对于原式
\[\sum_{d=1}^{\min\{n,m\}}\lfloor\frac nd\rfloor\mu(d)[d\perp K]\sum_{j=1}^{\lfloor\frac md\rfloor}[j\perp K] \]的相等的一块 \(d\in[l,r]\)，答案为
\[\begin{aligned} &\sum_{d=l}^r\lfloor\frac nl\rfloor\mathbf f(\lfloor\frac ml\rfloor)\mu(l)[l\perp K]\\ =&\lfloor\frac nl\rfloor\mathbf f(\lfloor\frac ml\rfloor)\sum_{d=l}^r\mu(l)[l\perp K]\\ =&\lfloor\frac nl\rfloor\mathbf f(\lfloor\frac ml\rfloor)(\mathbf g(r,K)-\mathbf g(l-1,K)) \end{aligned}\]下面分析用大写字母表示输入。
具体实现用杜教筛时我没有手写哈希，因为传入参数可能是 \(\lfloor\dfrac Nx\rfloor\) 也可能是 \(\lfloor\dfrac Mx\rfloor\)，学习笔记里提到的哈希函数不可用，我也没有找到合适的哈希函数。所以直接用了 unordered_map。
\(\mathbf g(n,k)\) 中的 \(k\) 显然只可能是 \(K\) 的因数，在 \(2000\) 以内的数中因数最多的为 \(1680\)，只有 \(40\) 个（可以写一个暴力算出来），而 \(n\) 只可能是 \(\lfloor\dfrac Nx\rfloor\) 或者 \(\lfloor\dfrac Mx\rfloor\)，最多只有 \(2\sqrt N+2\sqrt M\) 种取值（并且远远不会达到这个上界），所以状态只有 \(\mathcal O(\mathbf d(K)(\sqrt N+\sqrt M))\) 种，假设 \(N,M\) 同级，时间复杂度为 \(\mathcal O(K\log K+\mathbf d(K)\sqrt N+N^{\frac 23})\)，可以通过。
代码如下。
#include<cstdio>
#include<algorithm>
#include<vector>
#include<unordered_map>
using namespace std;
typedef long long ll;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
const int N=1e6,MK=2e3+5,sN=3.2e4,MAXN=1e9+1;
ll H(int n,int k){return (ll)MAXN*k+n;}
int K,v[N+1],mu[N+1],f[MK],S[N+1];
vector<int>pr;unordered_map<ll,int>g;
inline void init(){
for(int i=1;i<=K;i++)f[i]=f[i-1]+(gcd(K,i)==1?1:0);
S[1]=mu[1]=1;for(int i=2;i<=N;i++){
if(!v[i])pr.push_back(v[i]=i),mu[i]=-1;
for(int p:pr){
if(p>v[i]||p>N/i)break;
v[i*p]=p;
if(p==v[i])break;
mu[i*p]=-mu[i];
}
S[i]=S[i-1]+mu[i];
}
}
inline int F(int n){
return (n/K)*f[K]+f[n%K];}
int G(int n,int k){
if(!n)return 0;
ll p=H(n,k);if(g[p])return g[p];
if(k==1){
if(n<=N)return g[p]=S[n];
int ret=1;for(int l=2,r;l<=n;l=r+1){
r=n/(n/l);ret-=G(n/l,1)*(r-l+1);
}
return g[p]=ret;
}
int ret=0;
for(int d=1;d*d<=k;d++){
if(k%d)continue;
if(mu[d])ret+=G(n/d,d);
if(((d*d)^k)&&mu[k/d])ret+=G(n/(k/d),k/d);
}
return g[p]=ret;
}
int main(){
int n,m,mn;scanf("%d%d%d",&n,&m,&K);
init();ll ans=0;mn=min(n,m);
for(int l=1,r,x1,x2=0;l<=mn;l=r+1){
r=min(n/(n/l),m/(m/l));x1=G(r,K);
ans+=(ll)(x1-x2)*(n/l)*F(m/l);x2=x1;
}
printf("%lld\n",ans);
return 0;
}