0%

SHU426 膜两下将会让你送命

题目链接

欧拉函数$\phi(n)$被定义$1$~$n$中与$n$互质的数的个数。例如$\phi(5)=4$,因为$1$,$2$,$3$,$4$这四个数字与$5$互质。
定义$f$函数:$$f(n, k)=\sum\limits_{i=k}^{n-k}\phi(i) \cdot \lfloor \frac{n}{i} \rfloor$$
给定$n$和$k$,其中$2\le n\le 10^{12}$,$1\le k\le min(\lfloor\frac{n}{i}\rfloor,1000000)$,求$f(n,k)$的值。

简化公式

一看到这个就想到了求欧拉函数的前缀和然后杜教筛之类的。
但是当我着手做的时候发现这个$n$太大了,$O(n^{\frac{3}{4}})$的复杂度无法忍受。
于是我就想到这个$\lfloor\frac{n}{i}\rfloor$一定是有什么作用的,于是发现了一些不得了的事。


$$g(n)=\sum\limits_{i=1}^{n}\phi(i) \cdot \lfloor \frac{n}{i} \rfloor$$
$$=\sum\limits_{i=1}^{n}\phi(i)\sum\limits_{j=1}^{\lfloor\frac{n}{i}\rfloor}1$$
$$=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{\lfloor\frac{n}{i}\rfloor}\phi(i)$$

重头戏来了,这个式子特别像使用杜教筛时中间的某个式子,于是我们可以把它逆过来用

$$g(n)=\sum\limits_{i=1}^{n}\sum\limits_{d|i}\phi(d)$$
$$=\sum\limits_{i=1}^{n}i=\frac{n\cdot(n+1)}{2}$$

那么
$$f(n,k)=g(n)-\sum\limits_{i=1}^{k-1}\phi(i) \cdot \lfloor \frac{n}{i} \rfloor-\sum\limits_{i=n-k+1}^{n}\phi(i) \cdot \lfloor \frac{n}{i} \rfloor$$
$$=\frac{n\cdot(n+1)}{2}-\sum\limits_{i=1}^{k-1}\phi(i) \cdot \lfloor \frac{n}{i} \rfloor-\sum\limits_{i=n-k+1}^{n}\phi(i) \cdot \lfloor \frac{n}{i} \rfloor$$

然后我们就可以先用欧拉筛求出$\sqrt{n}$内的欧拉函数值以及所有的素数。然后用区间筛求出区间$[n-k+1,n]$之间的欧拉函数值。

复杂度$O(\sum\limits_{p\le \sqrt{n}}\lfloor\frac{k}{p}\rfloor+k+\sqrt{n})\approx O(能过)$

小技巧

在处理$(a×b×…)%m$时粗心的小伙伴总会因为太复杂而出错。
这样写基本上就不会出错了。
虽然可能会比较慢,但一般不会卡这个常吧。

1
2
3
4
5
6
7
8
9
10
11
long long mod(long long x, long long p) {
return ((x % p) + p) % p;
}

long long mmod() {
return 1ll;
}
template<typename T, typename ...U>
long long mmod(const T & head, const U &... tail) {
return mod((head % MOD) * mmod(tail...), MOD);
}

使用方法long long res = mmod(a, b, c, d);

AC代码

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
#include<bits/stdc++.h>
using namespace std;

struct Seive {
int maxn;
vector<bool> isp;
vector<int> p, phi;

Seive(int n = 0) : maxn(n), isp(n + 5), phi(n + 5) {
for (int i = 0; i < n + 5; i++) {
isp[i] = true;
phi[i] = 0;
}
solve();
}

void solve() {
isp[0] = isp[1] = false;
phi[1] = 1;
for (int i = 2; i <= maxn; i++) {
if (isp[i]) p.push_back(i), phi[i] = i - 1;
for (int j = 0; j < (int)p.size() && i * p[j] <= maxn; j++) {
isp[i * p[j]] = false;
if (i % p[j]) {
phi[i * p[j]] = phi[i] * (p[j] - 1);
} else {
phi[i * p[j]] = phi[i] * p[j];
break;
}
}
}
}
};

const long long MOD = 998244353ll;
long long mod(long long x, long long p = MOD) {
return ((x % p) + p) % p;
}
long long mmod() {
return 1ll;
}
template <typename T, typename... U>
long long mmod(const T &head, const U &... tail) {
return mod((head % MOD) * mmod(tail...), MOD);
}

int main() {
#ifdef ONLINE_JUDGE
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#define endl '\n'
#endif

Seive o(1000005);

long long n, k;
cin >> n >> k;

long long ans = mmod(n, n + 1, 499122177ll);
for(int i = 1; i < k; i++) {
ans = mod(ans - (n / i) % MOD * o.phi[i] % MOD, MOD);
}

vector<long long>v1(k + 1), v2(k + 1); // delta == n - k
for(int i = 1; i < k + 1; i++) {
v1[i] = v2[i] = n - k + i;
}
for(auto &x: o.p) {
for(long long m = (n - k) / x * x + x; m <= n; m += x) {
v1[m - (n - k)] -= v1[m - (n - k)] / x;
while(v2[m - (n - k)] % x == 0) {
v2[m - (n - k)] /= x;
}
}
}
for(int i = 1; i < k + 1; i++) {
if(v2[i] > 1) {
v1[i] -= v1[i] / v2[i];
}
}
for(long long i = n - k + 1; i <= n; i++) {
ans = mod(ans - (v1[i - (n - k)] % MOD) * (n / i) % MOD, MOD);
}
cout << ans << endl;
}

回到开头