【题解】uoj#221 [NOI2016]循环之美

给定 $n, m, k$,求有多少数值上互不相等的可以表示成 $\frac{x}{y}$ 的数, 满足 $1 ≤ x ≤ n$,$1 ≤ y ≤ m$,且其在 $k$ 进制下是纯循环小数。

特别的,整数是纯循环小数。 $1 ≤ n, m ≤ 10^9,2 ≤ k ≤ 2000$ 。

考虑本质上小数是如何产生的,发现就是当 $x/y$ 除到不能除时,$k$ 进制下,$x\times k$ 之后继续除下去。那么假设循环节长度为 $L$ ,那么会有 $x\bmod y=x\cdot k^L\bmod y$ 。也就是解得 $k^L\equiv1(\bmod y)$ 。那么由于逆元唯一,所以存在这样的一个 $L$,也就是存在逆元的充要条件就是 $k \perp y$ 。

并且由于不算重,还要求 $x\perp y$ 。所以最后本质上是要求:

随便反演一下

考虑后面那个 $\sum$ 。若令

那么由于 $\gcd$ 的优秀性质 $\gcd(a,b)=\gcd(b,a\bmod b)$ 所以

这个转移本质上是在做一个分块。

那么考虑前半部分这个 $\sum $ 。发现如果要数论分块的话,需要快速求

这个东西。根据一个神奇的 $\mu$ 函数的性质 $\mu(ab)=[a\perp b]\mu(a)\mu(b)$,可以得到

那么这东西显然可以用一个类杜教筛状物来做,大致就是当 $k=1$ 时本质上就是在做一个杜教筛,当 $k>1$ 时只需要枚举 $x$ 的全部因子,这样转移最多有 $\sigma_0(k)$ 种,$k$ 也只会有 $\sigma_0(k)$ 个,递归做下去就好了。这样复杂度的上界是 $O(n^{\frac{2}{3}}+\sigma_0^2(k)\sqrt n)$ ,是一个极其松的上界。

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
#define mkp make_pair
#define pint pair<int,int>

const int N = 500010 ;
const int M = 1001000 ;

LL f[N] ;
LL G[N] ;
int cnt ;
int mu[M] ;
int pr[M] ;
int smu[M] ;
int chk[M] ;
int n, m, k ;
map<pint, int> S ;

int gcd(int x, int y){
return (!y) ? x : gcd(y, x % y) ;
}
LL F(int n, int k){
return 1ll * ((n / k) * f[k] + f[n % k]) ;
}
void sieve(int x){
mu[1] = 1 ;
for (int i = 2 ; i <= x ; ++ i){
if (!chk[i])
pr[++ cnt] = i, mu[i] = -1 ;
for (int j = 1 ; j <= cnt ; ++ j){
if (i * pr[j] > x) break ;
chk[i * pr[j]] = 1 ;
if (i % pr[j] == 0) break ;
mu[i * pr[j]] = -mu[i] ;
}
}
for (int i = 1 ; i <= x ; ++ i)
smu[i] = smu[i - 1] + mu[i] ;
}
int s(int n, int k){
if (!n || (k == 1 && n < M))
return smu[n] ; int ans = 0 ;
pint t = mkp(n, k) ;
if (S.count(t)) return S[t] ;
if (k == 1){
ans = 1 ;
for (int l = 2, r ; l <= n ; l = r + 1){
r = n / (n / l) ;
ans -= (r - l + 1) * s(n / r, k) ;
}
}
else {
ans = 0 ;
for (int i = 1 ; i * i <= k ; ++ i){
if (k % i == 0){
if (mu[i]) ans += s(n / i, i) ;
if (i * i != k && mu[k / i])
ans += s(n / (k / i), k / i) ;
}
}
}
S[t] = ans ; return ans ;
}
LL solve(){
LL ans = 0, last = 0, now ;
for (int l = 1, r ; l <= n ; l = r + 1){
r = min(n / (n / l), m / (m / l)) ; now = s(r, k) ;
ans += (now - last) * (LL)(n / l) * F(m / l, k) ; last = now ;
}
return ans ;
}
int main(){
sieve(M - 1) ;
cin >> n >> m >> k ;
if (n > m) swap(n, m) ;
for (int i = 1 ; i <= k ; ++ i)
f[i] = f[i - 1] + (bool)(gcd(i, k) == 1) ;
printf("%lld\n", solve()) ; return 0 ;
}