「NOI2016」循环之美

发表于
https://loj.ac/problem/2085

题目链接

「NOI2016」循环之美

做法

设 $ k $ 进制下循环位数为 $ a $ ，则 $ xk^a \equiv x (\mod y) $ ，即 $ k^a \equiv 1 (\mod y) $ ，则 $ \gcd(k, y) = 1 $ 。
$$
Ans = \sum_{i = 1}^{n}\sum_{j = 1}^{m}[(i, j) = 1][(j, k) = 1]\\
= \sum_{j = 1}^{m}[(j, k) = 1]\sum_{i = 1}^{n}[(i, j) = 1]\\
= \sum_{j = 1}^{m}[(j, k) = 1]\sum_{i = 1}^{n}\sum_{d | (i, j)}\mu(d)\\
= \sum_{j = 1}^{m}[(j, k) = 1]\sum_{d | j}\mu(d)\lfloor \frac{n}{d} \rfloor\\
= \sum_{d = 1}^{\min(n, m)}\mu(d)\lfloor\frac{n}{d}\rfloor[(d, k) = 1]\sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor} [(j, k) = 1]\\
= \sum_{d = 1}^{\min(n, m)}\mu(d)\lfloor\frac{n}{d}\rfloor[(d, k) = 1]\sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor} \sum_{i | (j, k)} \mu(i)\\
= \sum_{d = 1}^{\min(n, m)}\mu(d)\lfloor\frac{n}{d}\rfloor[(d, k) = 1]\sum_{i| k} \lfloor \frac{m}{id} \rfloor .\\
f(n) = \sum_{i| k} \lfloor \frac{m}{i} \rfloor ,\\
Ans = \sum_{d = 1}^{\min(n, m)}\mu(d)\lfloor\frac{n}{d}\rfloor[(d, k) = 1] f(\lfloor \frac{m}{d} \rfloor)
$$
$ f(n) $ 可以枚举 $ k $ 的因数（$ k $ 很小）。
其中 $ \lfloor\frac{m}{d}\rfloor $ 和 $ \lfloor\frac{n}{d}\rfloor $ 可以整除分块。
$$
g(n, k) = \sum_{i = 1}^{n}\mu(i)[(i, k) = 1]\\
= \sum_{i = 1}^{n}\mu(i)\sum_{j | (i, k)}\mu(j)\\
= \sum_{i = 1}^{n}\sum_{j | (i, k)}\mu(i)\mu(j)\\
= \sum_{j | k}\mu(j)\sum_{i = 1}^{\lfloor\frac{n}{j}\rfloor}\mu(ij)\\
= \sum_{j | k}\mu(j)\sum_{i = 1}^{\lfloor\frac{n}{j}\rfloor}\mu(ij)[(i, j) = 1]\\
= \sum_{j | k}\mu^2(j)\sum_{i = 1}^{\lfloor\frac{n}{j}\rfloor}\mu(i)[(i, j) = 1]\\
= \sum_{j | k}\mu^2(j)g(\lfloor\frac{n}{j}\rfloor, j) .
$$

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
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 5000010;
ll n, m, k, d[N], ans = 0; int ld = 0;
vector<int> fac[2010];
ll mu[N], smu[N]; int p[N], lp = 0; bool pri[N];
map<ll, ll> Smu, F[2010];

template<typename T> void gi(T &x) {
	x = 0; register char c = getchar(), pre = 0;
	for(; c < '0' || c > '9'; pre = c, c = getchar());
	for(; c >= '0' && c <= '9'; c = getchar()) x = x * 10ll + (c ^ 48);
	if(pre == '-') x = -x;
}
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
void Sieve() {
	mu[1] = 1;
	rep(i, 2, N - 10) {
		if(!pri[i]) p[++lp] = i, mu[i] = -1;
		for(int j = 1; p[j] * i <= N - 10; ++j) {
			pri[p[j] * i] = 1; if(i % p[j] == 0) break;
			mu[p[j] * i] = -mu[i];
		}
	}
	rep(i, 1, N - 10) smu[i] = smu[i - 1] + mu[i];
	rep(i, 1, k) if(k % i == 0) d[++ld] = i;
	rep(i, 1, 2000) rep(j, 1, i) if(i % j == 0) fac[i].pb(j);
}
ll calc(ll x) {
	if(x <= N - 10) return smu[x]; if(Smu.count(x)) return Smu[x];
	ll sum = 1;
	for(ll l = 2, r; l <= x; l = r + 1) r = x / (x / l), sum -= (r - l + 1) * calc(x / l);
	return Smu[x] = sum;
}
ll f(ll x, ll y) {
	if(x < 2) return x; if(y == 1) return calc(x);
	if(F[y].count(x)) return F[y][x];
	ll sum = 0;
	for(auto v : fac[y]) if(mu[v]) sum += f(x / v, v);
	return F[y][x] = sum;
}
int main() {
	gi(n), gi(m), gi(k), Sieve();
	for(ll l = 1, r, sum; l <= min(n, m); l = r + 1) {
		r = min(n / (n / l), m / (m / l)), sum = 0;
		rep(j, 1, ld) sum += mu[d[j]] * (m / l / d[j]); sum *= (n / l);
		ans += sum * (f(r, k) - f(l - 1, k));
	}
	printf("%lld\n", ans);
	return 0;
}