Description：
牛牛是一个热爱算法设计的高中生。在他设计的算法中，常常会使用带小数的数进行计算。牛牛认为，如果在 k 进制下，一个数的小数部分是纯循环的，那么它就是美的。
现在，牛牛想知道：对于已知的十进制数 n 和 m，在 k 进制下，有多少个数值上互不相等的纯循环小数，可以用分数 $\frac{x}{y}$ 表示,其中 $1≤x≤n,1≤y≤m$，且 x,y 是整数。
一个数是纯循环的，当且仅当其可以写成以下形式：
$a.\dot{c_1} c_2 c_3 \ldots c_{p - 1} \dot{c_p}$
其中，a 是一个整数，$p≥1$；对于$ 1≤i≤p$，$c_i$ 是 k 进制下的一位数字。
例如，在十进制下，$0.45454545 \ldots \ldots = 0.\dot{4}\dot{5}$是纯循环的，它可以用 $\frac{5}{11}$$\frac{10}{22}$等分数表示；在十进制下，$0.1666666\ldots \ldots = 0.1\dot{6}$则不是纯循环的，它可以用 $\frac{1}{6}$ 等分数表示。
需要特别注意的是，我们认为一个整数是纯循环的，因为它的小数部分可以表示成 0 的循环或是 k−1 的循环；而一个小数部分非 0 的有限小数不是纯循环的。
Input：
输入文件只有一行，包含三个十进制数 n,m,k，意义如题所述。
Output：
只输出一行一个整数，表示满足条件的美的数的个数。
Hint：
对于所有的测试点，保证 $1≤n≤10^9,1≤m≤10^9,2≤k≤2000，1≤n≤10^9,1≤m≤10^9,2≤k≤2000$。
Analysis：
对于$\frac{x}{y}$，$(x, y) = 1$是纯循环的，当且仅当：
$k ^ l * \frac{x}{y} - \frac{x}{y} \in Z$
$(k ^ l - 1) * x \equiv 0 \pmod y$
$k ^ l \equiv 1 \pmod y$
即为$(y, k) = 1$, 所以转化为求解：
(请勿混淆下标与读入变量)
设$f_n = \sum_{i=1}^{n}[(i, k) = 1]$，又有
\begin{align}
& f_n= \lfloor \frac{n}{k} \rfloor f_k+f_{n\bmod k}
\end{align}
于是对于$f$进行$O(k^2)$预处理然后$O(n)$暴力可以水过84分
我们可以发现k的质因数不会超过4个，于是考虑从这里入手，设$k = p^c×q(p为质数)$
再设$g_{n, k} = \sum_{d=1}^{n} \mu(d)[(d, k)=1]$，
则有
于是可以递归处理计算函数$g$
对于边界：
1.n = 0时g = 0，
2.k = 1时用杜教筛算$\mu$的前缀和：
\begin{align}
&M(n) = \sum_{i=1}^{n} \mu(i) = 1 - \sum_{i=1}^{n} \sum_{d|i, d \ne i} \mu(d) = 1 - \sum_{i=2}^n M(\lfloor \frac{n}{i} \rfloor)
\end{align}
于是预处理出$n^{\frac{2}{3}}$中的$\mu$值，对于更大的范围，由于$\lfloor \frac{n}{i} \rfloor$只有$\sqrt{n}$种取值，从小到大每个需要$O(\sqrt{n})$的时间计算（可以保证$M(\lfloor \frac{n}{i} \rfloor$在之前算过了）。
时间复杂度$O(\omega(k) \sqrt{n} + n^{\frac{2}{3}})$，$\omega(k)$为质因数个数
最后对于$n, m$同时分段算答案就好了
Thought:
This is a beautiful problem！ Do you think so？
自己可以猜到那个巧妙的纯循环小数的性质><，感觉那个性质真的太美妙了！ 不愧是“循环之美”！
数论好厉害><，需要多推一些题目
Code：
//2017.5.25 Miaomiao
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
#define For(i, a, b) for(int i = (a); i <= (int)(b); ++i)
#define K (2000+5)
#define N (5000000+5)
const LL P = 100007;
int n, m, k, pn, mxp, f[K], prime[N], mypri[K];
int e1, e2, h1[15][P], h2[P], n1[N], n2[N];
LL mu[N], v1[N], v2[N], ag[N], as[N];
bool vis[N];
int gr;
inline int Gcd(int a, int b){
gr = a%b;
while(gr) a = b, b = gr, gr = a%b;
return b;
}
void Init(){
mu[1] = 1;
For(i, 2, N-1){
if(!vis[i]){prime[++pn] = i; mu[i] = -1;}
For(j, 1, pn){
if(prime[j]*i >= N) break;
vis[prime[j]*i] = true;
if(i % prime[j]) mu[i*prime[j]] = -mu[i];
else{mu[i*prime[j]] = 0; break;}
}
}
For(i, 2, N-1) mu[i] += mu[i-1];
For(i, 1, k) f[i] = f[i-1]+(Gcd(i, k)==1);
for(int i = 1; i <= pn && prime[i] <= k; ++i)
if(k%prime[i] == 0) mypri[++mxp] = prime[i];
}
inline LL CalcF(int nn){return (nn/k)*f[k]+f[nn%k];}
inline LL SumM(int nn){
if(nn < N) return (LL)mu[nn];
int mv = nn%P;
for(int i = h2[mv]; i; i = n2[i])
if(v2[i] == nn) return as[i];
v2[++e2] = nn; n1[e1] = h2[mv]; h2[mv] = e2;
LL &ret = v2[e2];
ret = 1ll;
for(int i = 2, nt = 0; i <= nn; i = nt+1){
nt = nn/(nn/i);
ret -= (LL)(nt-i+1)*SumM(nn/i);
}
return ret;
}
inline LL g(int nn, int nwp){
if(!nn) return 0;
if(!nwp) return SumM(min(nn, m));
int mv = nn%P;
for(int i = h1[nwp][mv]; i; i = n1[i])
if(v1[i] == nn) return ag[i];
v1[++e1] = nn; n1[e1] = h1[nwp][mv]; h1[nwp][mv] = e1;
return ag[e1] = g(nn, nwp-1) + g(nn/mypri[nwp], nwp);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
scanf("%d%d%d", &n, &m, &k);
Init();
int Min = min(n, m);
LL ans = 0, last = 0, now;
for(int d = 1, nt = 0; d <= Min; d = nt+1){
nt = min(n/(n/d), m/(m/d));
now = g(nt, mxp);
ans += (now-last)*(LL)(n/d)*CalcF(m/d);
last = now;
}
printf("%lld\n", ans);
return 0;
}