P1587 「NOI2016」循环之美

求 $\sum_{x=1}^n\sum_{y=1}^m\frac{x}{y}$ 在 $k$ 进制下能表示成循环节从第一位小数开始的无限循环小数或整数的最简分数个数

题解

题意转化

设 $l$ 为循环节长度，则

\frac{x}{y}k^l - \lfloor \frac{x}{y}k^l \rfloor= \frac{x}{y} - \lfloor \frac{x}{y} \rfloor

两边同时乘 $y$ 得

\begin{aligned} xk^l - \lfloor \frac{x}{y}k^l \rfloor \cdot y &= x - \lfloor \frac{x}{y} \rfloor \cdot y \\ xk^l - \lfloor \frac{x}{y}k^l \rfloor \cdot y &= x \bmod y \\ xk^l &\equiv x \pmod y \end{aligned}

由于 $x \perp y$

k^l \equiv 1 \pmod y

此方程有可行的 $l$ 当且仅当 $k \perp y$

所以题意转化成

\sum_{i=1}^n\sum_{j=1}^m[j \perp k][i \perp j]

正题

\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^m[j \perp k][i \perp j] \\ &\sum_{j=1}^m [j \perp k] \sum_{i=1}^n [i \perp j] \\ &\sum_{j=1}^m [j \perp k] \sum_{i=1}^n \sum_{d|(i,j)} \mu(d) \\ &\sum_{d=1}^n \mu(d) \sum_{d|i}^n\sum_{d|j}^m [j \perp k] \\ &\sum_{d=1}^n [d \perp k] \mu(d) \sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}} [j \perp k] \\ &\sum_{d=1}^n [d \perp k] \mu(d) \lfloor \frac{n}{d} \rfloor \sum_{j=1}^{\frac{m}{d}} [j \perp k] \end{aligned}

设 $f(x) = \sum_{j=1}^x [j \perp k]$ ，即 $[1,x]$ 中有多少个数和 $k$ 互质

考虑以 $k$ 分段，则 $f(x) = \lfloor \frac{x}{k} \rfloor \varphi(k) + f(x \bmod k)$ 注： $f(k) = \varphi(k)$

设 $S(x, k) = \sum_{i=1}^x [i \perp k] \mu(i)$

\begin{aligned} S(x, k) &= \sum_{i=1}^x [i \perp k] \mu(i) \\ &= \sum_{i=1}^x \sum_{d|(i,k)}\mu(d) \mu(i) \\ &= \sum_{d|k} \mu(d) \sum_{d|i}^x \mu(i) \\ &= \sum_{d|k} \mu(d) \sum_{i=1}^{\frac{x}{d}} \mu(id) \\ &= \sum_{d|k} \mu(d)^2 \sum_{i=1}^{\frac{x}{d}} [d \perp i]\mu(i) \\ &= \sum_{d|k} \mu(d)^2 S(\lfloor \frac{x}{d} \rfloor, d) \end{aligned}

当 $k = 1$ 时 $S(x,1) = \sum_{i=1}^x \mu(i)$

所以原式即为

\sum_{d=1}^n [d \perp k] \mu(d) \lfloor \frac{n}{d} \rfloor f(\lfloor\frac{m}{d}\rfloor)

后面的除法分块，前面的利用S（记忆化）求和

/// @tags: DujiaoSieve
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
using namespace std;

namespace BlueQuantum {

typedef long long ll;

int const N = 1e7 + 5, K = 2e3 + 5;

int n, k, m, cnt;
int f[K], pri[N], mu[N], smu[N];
bool vis[N];

map<pair<int, int>, int> mp;

inline void pre() {
  for (int i = 1; i <= k; ++i) f[i] = f[i - 1] + (__gcd(i, k) == 1);
  mu[1] = 1;
  for (int i = 2; i < N; ++i) {
    if (!vis[i]) pri[++cnt] = i, mu[i] = -1;
    for (int j = 1, x; j <= cnt && (x = i * pri[j]) < N; ++j) {
      vis[x] = true;
      if (i % pri[j] == 0) break;
      mu[x] = -mu[i];
    }
  }
  for (int i = 1; i < N; ++i) smu[i] = smu[i - 1] + mu[i];
}

inline int getF(int x) { return x / k * f[k] + f[x % k]; }

int getS(int x, int k) {
  if ((k == 1 && x < N) || (!x)) return smu[x];
  if (mp[make_pair(x, k)]) return mp[make_pair(x, k)];
  int res = 0;
  if (k == 1) {
    res = 1;
    for (int i = 2, j; i <= x; i = j + 1) {
      j = x / (x / i);
      res -= (j - i + 1) * getS(x / i, 1);
    }
  } else
    for (int i = 1; i * i <= k; ++i)
      if (k % i == 0) {
        if (mu[i]) res += getS(x / i, i);
        if (i * i != k && mu[k / i]) res += getS(x / (k / i), k / i);
      }
  return mp[make_pair(x, k)] = res;
}

inline int main() {
  cin >> n >> m >> k;
  pre();
  ll ans = 0, lstS = 0, curS = 0;
  for (int l = 1, r; l <= min(n, m); l = r + 1) {
    r = min(n / (n / l), m / (m / l));
    curS = getS(r, k);
    ans += (curS - lstS) * (n / l) * getF(m / l);
    lstS = curS;
  }
  cout << ans;
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P1587 [NOI2016] 循环之美.in", "r", stdin);
  freopen("P1587 [NOI2016] 循环之美.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}