膜两下将会让你送命(区间筛)

描述

传送门:EOJ 3349

欧拉函数 $\phi(n)$ 被定义 $1$~$n$ 中与 $n$ 互质的数的个数。例如 $\phi(5)=4$,因为 $1$, $2$, $3$, $4$ 这四个数字与 $5$ 互质。

定义 $f$ 函数: $$f(n, k)=\sum_{i=k}^{n-k}\phi(i) \cdot \lfloor \frac{n}{i} \rfloor$$

Input

输入一行,包含两个数字$n,k$,$2 \leq n \leq 10^{12}, 1 \leq k \leq \min([n/2], 1000000)$

Output

输出一行,表示函数值 $f(n,k)$ 膜 $998244353$。

Example

Input Output
1
1068 233
1
293824
1
972 233
1
222698
1
677621234681 566540
1
967258915

思路

$$\sum_{i=1} ^ {n} \phi(i) \cdot \lfloor \frac{n}{i} \rfloor = \sum_{i=1}^{n}n=\frac{n(n+1)}2$$

  • 所以我们只需要计算前$k$项和后$k$项,从答案里减掉就好了。
  • 由于$\phi(x) = x \prod (1 - \frac{1}{p_i})$。所以我们可以使用筛法求出前$k$项的欧拉函数。
  • 但是后$k$项就不好解决了,注意到$k$的范围,它的质因数除了本身,一定都在$10^6$以内,所以可以使用区间筛法来解决。
  • 最后把两段和减掉就好了。由于$n$比较大,所以取模的时候要格外小心,不要在乘法的时候爆long long了。

代码

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

#pragma optimize("-O3")

typedef long long ll;

void go();

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
go();
return 0;
}

/****************************************************************************************************/

const int N = 1 << 20;
ll phi[N] = {1, 1}, phi_big[N], t[N];

const int mod = 119 << 23 | 1;

ll Pow(ll a, ll n)
{
ll t = 1;
for (; n; n >>= 1, (a *= a) %= mod)
if (n & 1) (t *= a) %= mod;
return t;
}

void go()
{
ll n, k;
cin >> n >> k;
ll st = n - k;
for (int i = 0; i <= k; i++) phi_big[i] = t[i] = st + i;
for (int i = 2; i < N; i++)
if (!phi[i])
{
for (int j = i; j < N; j += i)
{
if (!phi[j]) phi[j] = j;
phi[j] = phi[j] / i * (i - 1);
}
for (ll j = st / i * i + i; j <= n; j += i)
{
ll k = j - st;
phi_big[k] = phi_big[k] / i * (i - 1);
while (t[k] % i == 0) t[k] /= i;
}
}
for (int i = 1; i <= k; i++)
if (t[i] > 1) phi_big[i] = phi_big[i] / t[i] * (t[i] - 1);
ll ans = (n % mod * ((n + 1) % mod)) % mod * Pow(2, mod - 2) % mod;
for (int i = 1; i <= k - 1; i++) ans = (ans - (phi[i] * ((n / i) % mod) % mod) + mod) % mod;
for (ll i = st + 1; i <= n; i++) ans = (ans - (phi_big[i - st] % mod * ((n / i) % mod) % mod) + mod) % mod;
cout << ans << endl;
}
捐助作者
0%