Description：

求分子 $\in[1,n]$ ，分母 $\in[1,m]$ 的在 $k$ 进制下化为小数后是纯循环小数的数的个数。

$1\leqslant n,m\leqslant 10^9,1\leqslant k\leqslant 2000$

Solution：

首先分数在 $k$ 进制下是纯循环小数当且仅当化为最简分数后分母中不含有 $k$ 的质因数。

那么我们可以列出答案的式子： $$ ans=\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1][\gcd(j,k)=1] $$ 如果没有 $[\gcd(j,k)=1]$ 的话就是一个入门反演，那么一般情况下这种问题的处理方法都是先忽略那一个特殊情况，和一般的一样处理其他的： $$ \begin{align} ans&=\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\sum_{d|i,d|j}\mu(d)\\ &=\sum_{d=1}^{\min(n,m)}\mu(d)\lfloor\frac n d\rfloor\sum_{j=1}^{\lfloor\frac m d\rfloor}[\gcd(jd,k)=1]\\ &=\sum_{d=1}^{\min(n,m)}\mu(d)[\gcd(d,k)=1]\lfloor\frac n d\rfloor\sum_{j=1}^{\lfloor\frac m d\rfloor}[\gcd(j,k)=1]\\ \end{align} $$ 然后我们需要停下来观察一下式子，最后面那个求和号好像和 $\varphi$ 很像： $$ f(n)=\sum_{i=1}^n[\gcd(i,k)=1] $$ 那么我们可以把这个式子每 $k$ 个划分成一段，显然每一段内与 $k$ 互质的个数是相同的，都是 $\varphi(k)$ ，因此： $$ f(n)=\varphi(k)\times\lfloor\frac n k\rfloor+f(n\text{ mod }k)=\varphi(k)\times\lfloor\frac n k\rfloor+\varphi(n\text{ mod }k) $$ 由于 $k$ 只有 $2000$ 因此可以预处理所有 $i<k$ 的 $f(i)$ 然后 $O(1)$ 计算。 $$ \begin{align} ans&=\sum_{d=1}^{\min(n,m)}\mu(d)[\gcd(d,k)=1]\lfloor\frac n d\rfloor f(\lfloor\frac m d\rfloor)\\ \end{align} $$ 然后我们发现如果我们可以求 $\mu(d)[\gcd(d,k)=1]$ 的前缀和那么就可以除法分块了。

再反演一下： $$ \begin{align} S(n,k)=&\sum_{i=1}^n\mu(i)[\gcd(i,k)=1]\\ =&\sum_{i=1}^n\sum_{d|i,d|k}\mu(d)\mu(i)\\ =&\sum_{d=1}^{\min(i,k)}\mu(d)[d|k]\sum_{i=1,d|i}^n\mu(i)\\ =&\sum_{d=1}^{\min(i,k)}\mu(d)[d|k]\sum_{i=1}^{\lfloor\frac n d\rfloor}\mu(id)\\ =&\sum_{d=1}^{\min(i,k)}\mu(d)[d|k]\sum_{i=1}^{\lfloor\frac n d\rfloor}[\gcd(i,d)=1]\mu(i)\mu(d)\\ =&\sum_{d|k}\mu(d)^2S(\lfloor\frac n d\rfloor,d) \end{align} $$ 这样就可以递归了，发现当 $k=1$ 的时候相当于 $\mu$ 的前缀和，杜教筛就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

int n,m,k;

#define MAXK 2010

#define MAX 1000010

#define N 1000000

bool isprime[MAX];

int prime[MAX],tot = 0;

int mu[MAX],phi[MAX];

int mus[MAX];

void sieve()

{

	for(int i = 2;i <= N;++i)isprime[i] = true;

	mu[1] = phi[1] = mus[1] = 1;

	for(int i = 2;i <= N;++i)

	{

		if(isprime[i])prime[++tot] = i,mu[i] = -1,phi[i] = i - 1;

		for(int j = 1;j <= tot && i * prime[j] <= N;++j)

		{

			isprime[i * prime[j]] = false;

			if(i % prime[j] == 0)

			{

				mu[i * prime[j]] = 0;

				phi[i * prime[j]] = phi[i] * prime[j];

				break;

			}

			else

			{

				mu[i * prime[j]] = -mu[i];

				phi[i * prime[j]] = phi[i] * phi[prime[j]];

			}

		}

		mus[i] = mus[i - 1] + mu[i];

	}

	return;

}

map<int,ll> mus_;

ll calc(int n)

{

	if(n == 1)return 1;

	if(n <= N)return mus[n];

	if(mus_.find(n) != mus_.end())return mus_[n];

	ll ans = 1;

	for(int l = 2,r;l <= n;l = r + 1)

	{

		r = n / (n / l);

		ans -= (r - l + 1) * calc(n / l);

	}

	return ans;

}

map<pair<int,int>,ll> S_;

ll S(int n,int k)

{

	if(k == 1)return calc(n);

	if(n == 0)return 0;

	if(S_.find(make_pair(n,k)) != S_.end())return S_[make_pair(n,k)];

	ll ans = 0;

	for(int i = 1;i * i <= k;++i)

	{

		if(k % i == 0)

		{

			if(mu[i] != 0)ans += S(n / i,i);

			if(i * i != k && mu[k / i] != 0)ans += S(n / (k / i),k / i);

		}

	}

	S_[make_pair(n,k)] = ans;

	return ans;

}

ll f_[MAXK];

ll f(int n)

{

	return f_[k] * (n / k) + f_[n % k];

}

int gcd(int a,int b){return (b == 0 ? a : gcd(b,a % b));}

int main()

{

	sieve();

	scanf("%d%d%d",&n,&m,&k);

	for(int i = 1;i <= k;++i)

		for(int j = 1;j <= i;++j)

			f_[i] += (gcd(k,j) == 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 += (S(r,k) - S(l - 1,k)) * (n / l) * f(m / l);

	}

	cout << ans << endl;

	return 0;

}