P1587 Solution
给你 \(n,m,k\)，求满足 \(1\le x\le n,1\le y\le m\) 且最简分数 \(\dfrac x y\) 是 \(k\) 进制下纯循环小数的二元组 \((x,y)\) 个数。
考虑纯循环小数的性质：我们知道纯循环小数的小数部分去除一个循环节后与原数的循环节相等，也就是
\[\frac x y-\left\lfloor\frac x y\right\rfloor=\frac{xk^l}y-\left\lfloor\frac{xk^l}y\right\rfloor \]其中 \(l\) 表示循环节长度，乘上 \(k^l\) 即将原数左移 \(l\) 位。那么
\[x-y\left\lfloor\frac x y\right\rfloor=xk^l-y\left\lfloor\frac{xk^l}y\right\rfloor \]\[x\equiv xk^l\pmod y \]因为 \(\dfrac x y\) 是最简分数，所以 \(\gcd(x,y)=1\)，所以
\[k^l\equiv 1\pmod y \]也就是 \(\gcd(k,y)=1\)。
于是要求的转化为
\[\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1][\gcd(j,k)=1] \]下面默认 \(n\le m\)。
\(\begin{aligned} \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1][\gcd(j,k)=1] &=\sum_{i=1}^n\sum_{j=1}^m\sum_{d|i}\sum_{d|j}\mu(d)[\gcd(j,k)=1]\\ &=\sum_{d=1}^n\mu(d)\sum_{i=1}^{\lfloor\frac n d\rfloor}\sum_{j=1}^{\lfloor\frac m d\rfloor}[\gcd(jd,k)=1]\\ &=\sum_{d=1}^n\mu(d)[\gcd(d,k)=1]\left\lfloor\frac n d\right\rfloor\sum_{j=1}^{\lfloor\frac m d\rfloor}[\gcd(j,k)=1]\\ \end{aligned}\)
设 \(\displaystyle f(n)=\sum_{i=1}^n[\gcd(i,k)=1]\)，由于有 \(\gcd(i+k,k)=\gcd(i,k)\)，我们可以把 \(f(n)\) 拆成若干长为 \(k\) 的段和最后剩下的一小段，也就是说
\[f(n)=\left\lfloor\frac n k\right\rfloor f(k)+f(n\bmod k) \]预处理 \(1\sim k\) 的 \(f\) 即可 \(\mathcal O(1)\) 得到 \(f\)。那么
\[\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1][\gcd(j,k)=1] =\sum_{d=1}^n\mu(d)[\gcd(d,k)=1]\left\lfloor\frac n d\right\rfloor f\left(\left\lfloor\frac m d\right\rfloor\right)\]现在只需要求出 \(\displaystyle\sum_{d=1}^n\mu(d)[\gcd(d,k)=1]\) 即可整除分块。设 \(\displaystyle g(n)=\sum_{d=1}^n\mu(d)[\gcd(d,k)=1]\)，于是
\[g(n)=\sum_{i=1}^n[\gcd(i,k)=1]g\left(\left\lfloor\frac n i\right\rfloor\right)-\sum_{i=2}^n[\gcd(i,k)=1]g\left(\left\lfloor\frac n i\right\rfloor\right) \]考虑前半部分
\(\begin{aligned} \sum_{i=1}^n[\gcd(i,k)=1]g\left(\left\lfloor\frac n i\right\rfloor\right) &=\sum_{i=1}^n[\gcd(i,k)=1]\sum_{j=1}^{\lfloor\frac n i\rfloor}\mu(j)[\gcd(j,k)=1]\\ &=\sum_{i=1}^n\sum_{j=1}^{\lfloor\frac n i\rfloor}\mu(j)[\gcd(ij,k)=1]\\ \end{aligned}\)
令 \(s=ij\)
\(\begin{aligned} \sum_{i=1}^n[\gcd(i,k)=1]g\left(\left\lfloor\frac n i\right\rfloor\right) &=\sum_{s=1}^n[\gcd(s,k)=1]\sum_{j|s}\mu(j)\\ &=\sum_{s=1}^n[\gcd(s,k)=1][s=1]\\ &=1 \end{aligned}\)
所以 \(\displaystyle g(n)=1-\sum_{i=2}^n[\gcd(i,k)=1]g\left(\left\lfloor\frac n i\right\rfloor\right)\)
这里 \([\gcd(i,k)=1]\) 的前缀和就是 \(f\)，所以整除分块递推计算即可。
复杂度大概是 \(\displaystyle\mathcal O(n^{\frac 3 4}+k)\) 的，预处理一部分的 \(g\) 可以做到 \(\displaystyle\mathcal O(n^{\frac 2 3}+k)\)。
代码
using namespace std;
const int N = 1e6 + 10;
const int inf = ~0u >> 2;
bool ip[N];
int mu[N],prime[N],cnt;
int f[N],g[N];
void sieve(int n)
{
cnt = 0;
memset( ip , true , sizeof(ip) );
ip[0] = ip[1] = false,mu[1] = 1;
for(int i = 2;i <= n;i++)
{
if( ip[i] )
prime[++cnt] = i,mu[i] = -1;
for(int j = 1;j <= cnt && i * prime[j] <= n;j++)
{
ip[ i * prime[j] ] = false;
if(i % prime[j] == 0)
break;
mu[ i * prime[j] ] = -mu[i];
}
}
}
int n,m,k;
int sum_f(int n)
{return f[k] * (n / k) + f[n % k];}
unordered_map<int , int> mp;
int sum_g(int n)
{
if(n <= N - 10)
return g[n];
if( mp.find(n) != mp.end() )
return mp[n];
int l = 2,r,res = 1;
while(l <= n)
{
r = n / (n / l);
res -= ( sum_f(r) - sum_f(l - 1) ) * sum_g(n / l);
l = r + 1;
}
return mp[n] = res;
}
LL h(int n , int m)
{
int l = 1,r;
LL res = 0;
while( l <= min(n , m) )
{
r = min( n / (n / l) , m / (m / l) );
res += 1ll * ( sum_g(r) - sum_g(l - 1) ) * (n / l) * sum_f(m / l);
l = r + 1;
}
return res;
}
int main()
{
sieve(N - 10);
cin >> n >> m >> k;
for(int i = 1;i <= k;i++)
f[i] = f[i - 1] + (__gcd(i , k) == 1);
for(int i = 1;i <= N - 10;i++)
g[i] = g[i - 1] + mu[i] * ( sum_f(i) - sum_f(i - 1) );
cout << h(n , m) << endl;
return 0;
}