Description
题库链接
给出十进制下的 \(n,m,k\) ，求 \(\frac{i}{j},i\in[1,n],j\in[1,m]\) 在 \(k\) 进制下不同的纯循环小数个数。
纯循环小数定义为该数小数点后全部都是循环节。
\(1\leq n,m\leq 10^9,1\leq k\leq 2000\)
Solution
首先考虑怎样的 \(\frac{x}{y}\) 会满足“纯循环”小数。
比较显然的是（题目中给出了提示）只要 \(\exists a\in\mathbb{N^*}\)
\[\begin{aligned}x&\equiv x\cdot k^a&\pmod{y}\\1&\equiv k^a&\pmod{y}\end{aligned}\]
即 \(\gcd(k^a,y)=1\Rightarrow \gcd(k,y)=1\) 。
那么现在式子就变成求
\[\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1][\gcd(j,k)=1]\]
我们先把奇奇怪怪的东西丢一边，依照套路
\[\begin{aligned}\Rightarrow &\sum_{i=1}^n\sum_{j=1}^m\sum_{d\mid \gcd(i,j)}\mu(d)[\gcd(j,k)=1]\\=&\sum_{d=1}^{\min\{n,m\}}\mu(d)\left\lfloor\frac{n}{d}\right\rfloor\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}[\gcd(jd,k)=1]\end{aligned}\]
由于 \(\gcd(jd,k)=1\Leftrightarrow \gcd(j,k)=1\wedge\gcd(d,k)=1\) ，那么
\[\Rightarrow \sum_{d=1}^{\min\{n,m\}}[\gcd(d,k)=1]\mu(d)\left\lfloor\frac{n}{d}\right\rfloor\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}[\gcd(j,k)=1]\]
不妨记 \(\sum\limits_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}[\gcd(j,k)=1]=F\left(\left\lfloor\frac{m}{d}\right\rfloor\right)\) ，注意到 \(\gcd(j,k)=\gcd(j-k,k)\) ，那么这个 \(F\) 很好求
\[F(n)=\left\lfloor\frac{n}{k}\right\rfloor f(k)+f(n\bmod{k})\]
其中 \(f(n)\) 表示 \(\sum\limits_{j=1}^{\min\{n,k\}}[\gcd(j,k)=1]\) 。这个可以 \(O(k\log(k))\) 预处理出来。 \(O(1)\) 回答询问。
那么原式变成
\[\sum_{d=1}^{\min\{n,m\}}\left\lfloor\frac{n}{d}\right\rfloor F\left(\left\lfloor\frac{m}{d}\right\rfloor\right)[\gcd(d,k)=1]\mu(d)\]
记 \([\gcd(d,k)=1]\mu(d)=g(d)\) ，考虑如何求 \(g(d)\) 。
这里比较巧妙，我们假设 \(M(n)=\sum\limits_{i=1}^n \mu(i)\) 。可以得到
\[\begin{aligned}g(n)&=M(n)-\sum_{i=2}^{\min\{k,n\}}[i\mid k]\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}[\gcd(j,k)=1]\mu(ji)\\&=M(n)-\sum_{i=2}^{\min\{k,n\}}[i\mid k]\mu(i)\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}[\gcd(j,k)=1]\mu(j)\\&=M(n)-\sum_{i=2}^{\min\{k,n\}}[i\mid k]\mu(i)g(\left\lfloor\frac{n}{d}\right\rfloor)\end{aligned}\]
那么可以枚举 \(k\) 的因数类似于杜教筛来求解。
复杂度为 \(O\left(n^{\frac{2}{3}}+\sigma_0(k)\sqrt{n}\right)\) 。
Code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 233333+5;
int n, m, k, mu[N], prime[N], isprime[N], tot;
map<int, ll>mmu, mg; ll ans;
int f[N], sum[N], g[N], factor[N], cnt;
int gcd(int a, int b) {return b ? gcd(b, a%b) : a; }
void get() {
memset(isprime, 1, sizeof(isprime));
isprime[1] = 0; mu[1] = g[1] = sum[1] = 1;
for (int i = 2; i < N; i++) {
if (isprime[i]) mu[prime[++tot] = i] = -1;
for (int j = 1; j <= tot && i*prime[j] < N; j++) {
if (i%prime[j]) mu[i*prime[j]] = -mu[i];
isprime[i*prime[j]] = 0;
if (i%prime[j] == 0) break;
}
sum[i] = sum[i-1]+mu[i]; g[i] = g[i-1];
if (gcd(i, k) == 1) g[i] += mu[i];
}
for (int i = 1; i <= k; i++) {
f[i] = f[i-1]; if (gcd(i, k) == 1) ++f[i];
if (k%i == 0 && i != 1) factor[++cnt] = i;
}
}
ll gmu(int x) {
if (x < N) return sum[x];
if (mmu.count(x)) return mmu[x];
ll ans = 1;
for (int last, i = 2; i <= x; i = last+1) {
last = x/(x/i);
ans -= 1ll*(last-i+1)*gmu(x/i);
}
return mmu[x] = ans;
}
ll gg(int x) {
if (x < N) return g[x];
if (mg.count(x)) return mg[x];
ll ans = gmu(x);
for (int i = 1; i <= cnt && factor[i] <= x; i++)
ans -= 1ll*mu[factor[i]]*gg(x/factor[i]);
return mg[x] = ans;
}
ll F(int x) {return 1ll*x/k*f[k]+f[x%k]; }
void work() {
scanf("%d%d%d", &n, &m, &k); get();
for (int last, i = 1; i <= min(n, m); i = last+1) {
last = min(n/(n/i), m/(m/i));
ans += 1ll*F(m/i)*(n/i)*(gg(last)-gg(i-1));
}
printf("%lld\n", ans);
}
int main() {work(); return 0; }