Description
给出(n,m(n,mleq10^9))和(k(kleq2000))，求在(k)进制下，有多少个数值不同的纯循环小数可以表示成(dfrac{x}{y})的形式，其中(xin[1,n],yin[1,m])。一个数是纯循环小数当且仅当它能写成(a.dot{c_1} c_2 c_3 ldots c_{p-1}dot{c_p})的形式。
Solution
原题相当于求有多少个数对((x,y))满足(gcd(x,y)=1)且(dfrac{x}{y})是纯循环小数。因为若(x,y)不互质且在范围内，将(dfrac{x}{y})化为最简分数依然在范围内。
首先考虑一个数是纯循环小数意味着什么。
[egin{align*}
a.dot{c_1} c_2 c_3 ldots c_{p-1}dot{c_p} &= a+sum_{i=0}^{+∞}(0.c_1c_2c_3ldots c_{p-1}c_p)_{k}cdot k^{-ip} \
&= a+(0.c_1c_2c_3ldots c_{p-1}c_p)_{k}sum_{i=0}^{+infty}(k^{-p})^i \
&= a+frac{1}{1-k^{-p}}(0.c_1c_2c_3ldots c_{p-1}c_p)_{k} \
&= a+frac{(c_1c_2c_3ldots c_{p-1}c_p)_k}{k^p-1} \
frac{x}{y} &= a+frac{(c_1c_2c_3ldots c_{p-1}c_p)_k}{k^p-1} \
lfloor frac{x}{y}
floor + frac{x mod y}{y} &= a+frac{(c_1c_2c_3ldots c_{p-1}c_p)_k}{k^p-1}
end{align*}$$ 令$a=lfloor dfrac{x}{y}
floor$，那么若$dfrac{x mod y}{y}$能表示成$dfrac{(c_1c_2c_3ldots c_{p-1}c_p)_k}{k^p-1}$的形式则说明$dfrac{x}{y}$是纯循环小数。由于$dfrac{x mod y}{y}$是最简分数，所以$dfrac{x}{y}$是纯循环小数 ⇔ $exists p$使得$y|k^p-1$ ⇔ $exists p$使得$k^p mod y = 1$ ⇔ $gcd(y,k)=1$。
于是原题相当于求
$$egin{align*}
ans &= sum_{x=1}^n sum_{y=1}^n [gcd(x,y)=1][gcd(y,k)=1] \
&= sum_{d=1}^{+∞} mu(d) sum_{d|x}^n sum_{d|y}^m [gcd(y,k)=1] \
&= sum_{d=1}^{+∞} mu(d) lfloorfrac{n}{d}
floor sum_{i=1}^{lfloorfrac{m}{d}
floor} [gcd(id,k)=1] \
&= sum_{d=1}^{min(n,m)} [gcd(d,k)=1]mu(d) lfloorfrac{n}{d}
floor sum_{i=1}^{lfloorfrac{m}{d}
floor} [gcd(i,k)=1] \
end{align*}$$于是我们发现我们主要要求两个东西：$f(x,k)=sum_{i=1}^x [gcd(i,k)=1]$和$g(x,k)=sum_{i=1}^x [gcd(i,k)=1]mu(i)$。算出他们就可以利用整除分块来快速计算。
易知$f(x,k)=lfloordfrac{x}{k}
floor f(k,k)+f(xmod k,k)$，而对于$xin[0,k]$我们都可以预处理出来，所以$f$很好求。
考虑$g$怎么求。将$k$表示成$p^tq$的形式，其中$p$是质数，$gcd(p,q)=1$。那么$gcd(i,k)=1 ⇔ gcd(i,p)=1,gcd(i,q)=1$。那么我们从满足$gcd(i,q)=1$的$i$中减去$gcd(i,p)
eq1$即$p|i$的部分，即：
$$egin{align*}
g(x,k) &= sum_{i=1}^x[gcd(i,q)=1]mu(i)-sum_{p|i}^x[gcd(i,q)=1]mu(i) \
&= g(x,q)-sum_{i=1}^{lfloorfrac{x}{p}
floor}[gcd(ip,q)=1][gcd(i,p)=1]mu(ip) \
&= g(x,q)-sum_{i=1}^{lfloorfrac{x}{p}
floor}[gcd(i,k)=1]mu(i)mu(p) \
&= g(x,q)-g(lfloorfrac{x}{p}
floor,k)
end{align*}$$ 易知$g(x,1)=sum_{i=1}^x mu(i)$，可以用杜教筛来求。用`map`或哈希表来对$g$进行存储以进行记忆化搜索，就可以通过本题啦。
##Code
```cpp
//「NOI2016」循环之美
#include <cstdio>
#include <map>
using namespace std;
const int N=3e6+10;
int n,m,k;
int gcd(int x,int y) {return x%y?gcd(y,x%y):y;}
int f0[2001];
void initF() {for(int i=1;i<=k;i++) f0[i]=f0[i-1]+(gcd(i,k)==1);}
int f(int x) {return x/k*f0[k]+f0[x%k];}
int prCnt,pr[N]; bool prNot[N];
int muS[N];
void initG(int n)
{
muS[1]=1;
for(int i=2;i<=n;i++)
{
if(!prNot[i]) pr[++prCnt]=i,muS[i]=-1;
for(int j=1;j<=prCnt;j++)
{
int x=i*pr[j]; if(x>n) break;
prNot[x]=true;
if(i%pr[j]) muS[x]=-muS[i]; else break;
}
}
for(int i=1;i<=n;i++) muS[i]+=muS[i-1];
}
map<pair<int,int>,int> g1;
map<pair<int,int>,bool> getG;
int sum(int x)
{
pair<int,int> x_1=make_pair(x,1);
if(x<=2e6) return g1[x_1]=muS[x];
if(getG[x_1]) return g1[x_1];
lint res=1;
for(int L=2,R;L<=x;L=R+1)
{
int v=x/L; R=x/v;
res-=1LL*(R-L+1)*sum(v);
}
getG[x_1]=true;
return g1[x_1]=res;
}
int g(int x,int k)
{
pair<int,int> x_k=make_pair(x,k);
if(getG[x_k]) return g1[x_k];
if(x==0||k==1) return sum(x);
int p,q;
for(int i=1;i<=prCnt;i++) if(k%pr[i]==0) {p=pr[i]; break;}
q=k; while(q%p==0) q/=p;
getG[x_k]=true;
int r=g(x,q)+g(x/p,k);
return g1[x_k]=r;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
int n0=min(n,m);
initF(); initG(2e6);
long long ans=0;
for(int L=1,R;L<=n0;L=R+1)
{
int v1=n/L,v2=m/L; R=min(n/v1,m/v2);
ans+=1LL*(g(R,k)-g(L-1,k))*v1*f(v2);
}
printf("%lld
",ans);
return 0;
}
```
##P.S.
本题中$n,m$的意义不等价，不可以互换...我以前为了简洁经常是用`swap`钦定$n<m$，结果这题鸽了一周看不出来锅...]