UOJ 221「NOI2016」循环之美

发表于 | 分类于

Description

求有多少数值不同的分数\(\frac{x}{y}\)（\(1\leq x\leq n, 1\leq y\leq m\)），满足其在\(k\)进制下化为小数之后事纯循环小数（即小数部分是无限循环的）。

\(1\leq n, m\leq 10^9,2\leq k\leq 2000\)。

Solution

首先如果只统计最简分数就能保证数值相同辣（即钦点\(x\perp y\)，这里用垂直符号表示互质）。然后通过猜结论等手段可以发现纯循环小数其实限制了\(y\perp k\)。

然后考虑颓柿子： \[ \begin{aligned} \quad&\sum_{x = 1}^n\sum_{y = 1}^m [x\perp y][y\perp k]\\ =&\sum_{x = 1}^n\sum_{y = 1,y\perp k}^m \sum_{d | x, d | y}\mu(d)\\ =&\sum_{d = 1,d\perp k}^{\min(n, m)}\mu(d)\lfloor\frac{n}{d}\rfloor\sum_{y = 1}^{\lfloor\frac{m}{d}\rfloor}[y\perp k] \end{aligned} \] 然后这样是个反演的形式……很容易想到数论分块罢……

接下来首先要考虑对于所有\(\lfloor\frac{m}{d}\rfloor\)处理出范围内和\(k\)互质的数的数量，这个很容易想到洲阁筛的思路。考虑筛出\(k\)的所有质因子\(p_1,p_2,\ldots,p_c\)，定义状态\(f(i, j)\)表示不大于\(j\)且和\(p_1, p_2,\ldots,p_i\)互质的数的数目（边界为\(f(0, j) = j\)）。然后转移很显然是： \[ f(i, j) = f(i - 1, j) - f(i - 1, \lfloor\frac{j}{p_i}\rfloor) \] 然后我们还有一块硬骨头……就是对于所有\(\lfloor\frac{n}{d}\rfloor\)要求出范围内和\(k\)互质的\(d\)的\(\mu(d)\)的和。还是采用洲阁筛的思路，定义\(g(i, j)\)表示对于所有\(d\)满足\(d\leq j\)且\(d\perp p_1, p_2,\ldots, p_i\)的\(\mu(d)\)的和，这样边界\(g(0, j)\)也就是直接对\(\mu\)求一个前缀和，这个杜教筛处理。其他情况的话，我们要排除在一个没有前\(i\)个质因子的数的基础上乘上\(p_i\)的情况（如果有\(p_i\)这个质因子的话再乘一遍就变成0了，所以对答案没有影响），故转移如下： \[ g(i,j)=g(i - 1, j) + g(i, \lfloor\frac{j}{p_i}\rfloor) \] 考虑到这题\(k\)不大，所以第一维非常的小，甚至不需要用洲阁筛的一般加速方法。总复杂度为\(O(n^\frac{2}{3} + \omega(k)\sqrt{n})\)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
#include <unordered_map>
using ll = long long;
const int N = 10000000;
int mu[N + 5]; int mu_S[N + 5];
int prm[N + 5]; bool vis[N + 5];
void process() {
  mu[1] = 1; vis[1] = true;
  int cnt = 0;
  for(int i = 2; i <= N; i ++) {
    if(!vis[i]) {
      prm[cnt ++] = i;
      mu[i] = -1;
    }
    for(int j = 0; j < cnt && i * prm[j] <= N; j ++) {
      int v = i * prm[j];
      vis[v] = true;
      if(i % prm[j] == 0) {
        mu[v] = 0; break;
      } else {
        mu[v] = -mu[i];
      }
    }
  }
  for(int i = 1; i <= N; i ++) {
    mu_S[i] = mu_S[i - 1] + mu[i];
  }
}

int p[12]; int pcnt;
void desc(int x) {
  pcnt = 0; int l = sqrt(x + 0.5);
  for(int i = 2; i <= l; i ++) {
    if(x % i == 0) {
      p[++ pcnt] = i;
      while(x % i == 0) x /= i;
    }
  }
  if(x > 1) p[++ pcnt] = x;
}

std::unordered_map<int, ll> h1[12];
ll calc_1(int c, int n) {
  if(c == 0) return n;
  if(n == 0) return 0;
  if(h1[c].count(n)) return h1[c][n];
  ll ret = calc_1(c - 1, n) - calc_1(c - 1, n / p[c]);
  h1[c][n] = ret;
  return ret;
}
std::unordered_map<int, ll> h2[12];
ll calc_2(int c, int n) {
  if(c == 0) {
    if(n <= N) return mu_S[n];
    if(h2[0].count(n)) return h2[0][n];
    ll ret = 1;
    for(int i = 2; i <= n;) {
      int next = n / (n / i);
      ret -= (ll(next - i  + 1)) * calc_2(0, n / i);
      i = next + 1;
    }
    h2[0][n] = ret;
    return ret;
  }
  if(n == 0) return 0;
  if(h2[c].count(n)) return h2[c][n];
  ll ret = calc_2(c - 1, n) + calc_2(c, n / p[c]);
  h2[c][n] = ret;
  return ret;
}
ll calc(int n, int m, int k) {
  desc(k); ll ans = 0;
  ll las = 0;
  for(int i = 1; i <= std::min(n, m);) {
    int next = std::min(n / (n / i), m / (m / i));
    ll th = n / i;
    th *= (ll)calc_1(pcnt, m / i);
    ll ts = calc_2(pcnt, next);
    th *= (ts - las);
    ans += th;
    i = next + 1; las = ts;
  }
  return ans;
}

int main() {
  process();
  int n, m, k; scanf("%d%d%d", &n, &m, &k);
  printf("%lld\n", calc(n, m, k));
  return 0;
}