Description
- 给定十进制数 \(n, m, k\)，求在 \(k\) 进制下有多少个 值不相等 的 纯循环 小数可以用分数 \(\dfrac{x}{y}\) 表示，其中 \(1\le x\le n, 1\le y\le m, x, y \in \mathbb{N}^*\)。
- \(1\le n, m\le 10^9, 2\le k\le 2\times 10^3\)。
Solution
Step 1：转化问题
首先这些数的值要互不相等，那不妨只计算满足要求的 最简分数 的数量，即 \(\gcd(x, y) = 1\)。
根据你丰富的小奥知识得到：如果在 \(k\) 进制下分数 \(\dfrac{x}{y}\) 为最简分数，则 \(\gcd(y, k) = 1\) 是其可化成纯循环小数的 充要条件。
证明：
设 \(\dfrac{x}{y}\) 化成的纯循环小数的循环节长度为 \(l\)，则有 \(\left\{\dfrac{x}{y} \right\} = \left\{\dfrac{x}{y} \cdot k^l \right\}\)。
乘 \(k^l\) 其实就是将小数点向后移动 \(l\) 位，小数部分还是不变的。
根据 \(\{x\} = x - \lfloor x\rfloor\)，有
\[\dfrac{x}{y} - \left\lfloor\dfrac{x}{y}\right\rfloor = \dfrac{x k^l}{y} - \left\lfloor\dfrac{x k^l}{y}\right\rfloor \\ x - \left\lfloor\dfrac{x}{y}\right\rfloor y = x k^l - \left\lfloor\dfrac{x k^l}{y} \right\rfloor y \\ x \equiv x k^l \pmod y \\ \because \gcd(x, y) = 1 \\ \therefore k^l \equiv 1 \pmod y \\ \therefore \gcd(y, k) = 1 \]
所以我们要求的其实就是
\[\sum_{x = 1}^n \sum_{y = 1}^m [\gcd(x, y) = 1] [\gcd(y, k) = 1] \]Step 2：莫比乌斯反演
先将 \(x \Leftrightarrow i, y \Leftrightarrow j\)，不妨设 \(n\le m\)。
\[\begin{aligned} ans & = \sum_{i = 1}^n \sum_{j = 1}^m [\gcd(j, k) = 1] \sum_{d\mid \gcd(i, j)} \mu(d) \\ & = \sum_{d = 1}^n \mu(d) \left\lfloor\dfrac{n}{d}\right\rfloor \sum_{j = 1}^{\left\lfloor\frac{m}{d}\right\rfloor} [\gcd(jd, k) = 1] \\ & = \sum_{d = 1}^n [\gcd(d, k) = 1] \mu(d) \left\lfloor\dfrac{n}{d}\right\rfloor \sum_{j = 1}^{\left\lfloor\frac{m}{d}\right\rfloor} [\gcd(j, k) = 1] \end{aligned} \]已经化到最简了，考虑设函数。
我们对
\[f(n) = \sum_{i = 1}^n [\gcd(i, k) = 1] \]很熟悉，因为它是每 \(k\) 个一循环，即
\[f(n) = \left\lfloor\dfrac{n}{k}\right\rfloor \varphi(k) + f(n\bmod k) \]又因为 \(0\le n\bmod k < k\)，所以可以 \(\Omicron(k\log k)\) 暴力预处理 \(f(0) \sim f(k)\)，\(f(k)\) 直接当 \(\varphi(k)\) 用。
将 \(f\) 代回原式
\[ans = \sum_{d = 1}^n [\gcd(d, k) = 1] \mu(d) \left\lfloor\dfrac{n}{d}\right\rfloor f\left(\left\lfloor\dfrac{m}{d}\right\rfloor \right) \]后面两项打包整除分块，
因为 \(n\le 10^9\)，明显需要杜教筛。
前面两项的前缀和
\[g(n) = \sum_{i = 1}^n [\gcd(i, k) = 1] \mu(i) \]用类似杜教筛的思路
\[\begin{aligned} g(n) & = [\gcd(1, k) = 1] g\left(\left\lfloor\dfrac{n}{1}\right\rfloor \right) \\ & = \sum_{i = 1}^n [\gcd(i, k) = 1] g\left(\left\lfloor\dfrac{n}{i}\right\rfloor \right) - \sum_{i = 2}^n [\gcd(i, k) = 1] g\left(\left\lfloor\dfrac{n}{i}\right\rfloor \right) \end{aligned} \]而后面一项中的 \([\gcd(i, k) = 1]\) 的前缀和其实就是已经处理过的 \(f\)！
所以只要处理出前面那一项就可以完全仿照杜教筛递归 + 记忆化计算了。
\[\begin{aligned} \sum_{i = 1}^n [\gcd(i, k) = 1] g\left(\left\lfloor\dfrac{n}{i}\right\rfloor \right) & = \sum_{i = 1}^n [\gcd(i, k) = 1] \sum_{j = 1}^{\left\lfloor\frac{n}{i}\right\rfloor} [\gcd(j, k) = 1] \mu(j) \\ & = \sum_{i = 1}^n \sum_{j = 1}^{\left\lfloor\frac{n}{i}\right\rfloor} [\gcd(ij, k) = 1] \mu(j) \\ & = \sum_{T = 1}^n [\gcd(T, k) = 1] \sum_{d\mid T} \mu(d) \\ & = \sum_{T = 1}^n [\gcd(T, k) = 1] (\mu * \mathbf{1})(T) \\ & = \sum_{T = 1}^n [\gcd(T, k) = 1] \varepsilon(T) \\ & = 1 \end{aligned} \]所以
\[g(n) = 1 - \sum_{i = 2}^n [\gcd(i, k) = 1] g\left(\left\lfloor\dfrac{n}{i}\right\rfloor \right) \]杜教筛即可做到 \(\Omicron(n^{\frac{2}{3}})\) 计算。
总时间复杂度为 \(\Omicron(k\log k + n^{\frac{2}{3}})\)。
Tips : You should use long long .
Warning : You cannot swap(n, m) !!!
Code
//18 = 9 + 9 = 18.
#include <iostream>
#include <cstdio>
#include <unordered_map>
#define Debug(x) cout << #x << "=" << x << endl
#define int long long
using namespace std;
const int MAXN = 1e6 + 5;
const int N = 1e6;
const int MAXK = 2e3 + 5;
const int K = 2e3;
int k;
int p[MAXN], mu[MAXN], g[MAXN], f[MAXK];
bool vis[MAXN];
int GetF(int n)
{
return n / k * f[k] + f[n % k];
}
int gcd(int a, int b)
{
if (!b)
{
return a;
}
return gcd(b, a % b);
}
void pre()
{
for (int i = 1; i <= k; i++)
{
f[i] = f[i - 1] + (gcd(i, k) == 1);
}
mu[1] = g[1] = 1;
for (int i = 2; i <= N; i++)
{
if (!vis[i])
{
p[++p[0]] = i;
mu[i] = -1;
}
g[i] = g[i - 1] + (GetF(i) - GetF(i - 1)) * mu[i];
for (int j = 1; j <= p[0] && i * p[j] <= N; j++)
{
vis[i * p[j]] = true;
if (i % p[j] == 0)
{
mu[i * p[j]] = 0;
break;
}
mu[i * p[j]] = mu[i] * mu[p[j]];
}
}
}
int GetSumF(int l, int r)
{
return GetF(r) - GetF(l - 1);
}
unordered_map<int, int> dp;
int sublinear(int n)
{
if (n <= N)
{
return g[n];
}
if (dp.count(n))
{
return dp[n];
}
int res = 1;
for (int l = 2, r; l <= n; l = r + 1)
{
int k = n / l;
r = n / k;
res -= GetSumF(l, r) * sublinear(k);
}
return dp[n] = res;
}
int GetSumG(int l, int r)
{
return sublinear(r) - sublinear(l - 1);
}
int block(int n, int m)
{
int res = 0;
for (int l = 1, r; l <= n; l = r + 1)
{
int k1 = n / l, k2 = m / l;
if (!k2)
{
break;
}
r = min(n / k1, m / k2);
res += GetSumG(l, r) * k1 * GetF(k2);
}
return res;
}
signed main()
{
int n, m;
scanf("%lld%lld%lld", &n, &m, &k);
pre();
printf("%lld\n", block(n, m));
return 0;
}