原文创建时间：2021-02-24 01:06:31
题目链接
Problem 625
题意
定义
$$\displaystyle f(n) = \sum_{1 \leq i \leq j \leq n} \gcd(i,j)$$
求
$$f\left(10^{11}\right) \bmod 998244353$$
解
我们知道，$f(n)$ 可以变换成
$$\displaystyle \sum_{d=1}^nd\sum_{i=1}^n\varphi(i)$$
推导可见这里，题目的差异仅在于 $i < j$ 和 $i \leq j$。
$n = 10^{11}$ 较大，无法线性存储，故使用杜教筛。
杜教筛求 $\varphi$ 前缀和 $S(n)$：
由 $1 \ast \varphi = id$，构造 $f = \varphi,\ g = 1$，可得
$$\displaystyle S(n) = \frac{n(n+1)}{2} - \sum_{i=2}^nS\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$$
代码
Project Euler 网站限制程序应在 1 min 内出结果 （太宽裕啦），所以没想什么优化，也没怎么管算法复杂度。
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>
#define REG register
using namespace std;
namespace ACAH
{
typedef __int128 ql;
const ql N = 1e11;
const int p = 998244353;
const int bd = 1e7;
const int maxn = 1e7 + 7;
int pr[maxn], pc;
bool ip[maxn];
ql phi[maxn];
map<ql, ql> sphi;
ql ans;
void linear_sieve()
{
phi[1] = 1;
for(REG int i = 2; i <= bd; i++) {
if(!ip[i]) pr[++pc] = i, phi[i] = i - 1;
for(REG int j = 1; j <= pc && 1ll * i * pr[j] <= bd; j++) {
REG int cr = i * pr[j];
ip[cr] = true;
if(i % pr[j]) phi[cr] = phi[i] * (pr[j] - 1);
else {phi[cr] = phi[i] * pr[j]; break;}
}
}
for(REG int i = 2; i <= bd; i++) phi[i] += phi[i - 1], phi[i] %= p;
}
inline ql getphi(ql x)
{
if(x <= bd) return phi[x];
if(sphi[x]) return sphi[x];
REG ql res = 0;
for(REG ql l = 2, r; l <= x; l = r + 1) {
r = x / (x / l);
res += (r - l + 1) * getphi(x / l) % p;
res %= p;
}
res = ((x * (x + 1) >> 1) % p - res + p) % p;
return sphi[x] = res;
}
int work()
{
linear_sieve();
for(REG ql l = 1, r; l <= N; l = r + 1) {
r = N / (N / l);
ans += (((l + r) * (r - l + 1) >> 1) % p) * getphi(N / l) % p;
ans %= p;
}
printf("%lld", (long long) ans);
return 0;
}
}
int main() {return ACAH::work();}
|
本题答案
$$551614306$$