题目描述
https://codeforces.com/contest/915/problem/G
Solution
$b_m=\sum_{i_1=1}^m\sum_{i_2=1}^m\cdots\sum_{i_n=1}^m[(i_1,i_2,\cdots,i_n)=1]$
我们套路化简得到
$b_m=\sum_{d=1}^m\mu(d)\sum_{d|i_1}\sum_{d|i_2}\cdots\sum_{d|i_n}1=\sum_{d=1}^m\mu(d){\lfloor\frac md\rfloor}^n$
如果我们预处理 $n$ 次幂，那么枚举 $m$ 能够做到 $O(n\sqrt n)$，但是这不足以通过此题
我们考虑枚举 $d$，注意到 ${\lfloor\frac md\rfloor}^n$ 对连续 $d$ 个数是相同的，那么这样做的复杂度就是 $O(k\log k)$
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
| #include <iostream>
#include <vector>
#define maxn 2000010
#define ll long long
using namespace std;
const int p = 1000000007;
ll pow_mod(ll x, ll n) {
ll s = 1;
for (; n; n >>= 1, x = x * x % p)
if (n & 1) s = s * x % p;
return s;
}
int n, k;
int pri[maxn], cnt, mu[maxn]; bool isp[maxn];
void init_isp(int n) {
mu[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!isp[i]) pri[++cnt] = i, mu[i] = -1;
for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
isp[i * pri[j]] = 1;
if (i % pri[j] == 0) break;
mu[i * pri[j]] = -mu[i];
}
}
}
ll s[maxn], _pow[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> k; init_isp(k);
for (int i = 1; i <= k; ++i) _pow[i] = pow_mod(i, n);
for (int i = 1; i <= k; ++i)
for (int j = i; j <= k; j += i) {
s[j] = (s[j] + mu[i] * _pow[j / i]) % p;
if (j + i <= k) s[j + i] = (s[j + i] - mu[i] * _pow[j / i]) % p;
}
ll ans = 0;
for (int i = 1; i <= k; ++i) {
s[i] = (s[i] + s[i - 1]) % p;
ans = (ans + ((s[i] + p) % p ^ i)) % p;
} cout << ans << "\n";
return 0;
}
|