题目描述
Link
Solution
第一个根本不用筛，答案永远都是1
现在来解决第二个：
我们先把 $\varphi(x ^ 2)$ 化简一下
我们知道，欧拉函数是这样计算的：
所以设 $x = p_1 ^ {a_1} p_2 ^ {a_2} p_3 ^ {a_3}…p_i ^ {a_i}$
所以有
所以
于是第二个就变成了
然后就可以用杜教筛了。
设 $f(i) = i \cdot \varphi(i)$，$g(n) = \sum_{i = 1}^n f(i)$
因为 $id = f * id$
所以
Code
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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <tr1/unordered_map>
#define MAXN 5001000
#define MOD 1000000007
#define ll long long
#define re register
#define int long long
using namespace std;
tr1::unordered_map<ll, ll> ans2;
int p[MAXN], phi[MAXN], tot, t, n;
ll pre2[MAXN], kk, tt;
bool chk[MAXN];
ll qpow(ll a, ll b, ll m) {
ll res = 1;
while (b) {
if (b & 1) res = (res * a) % m;
b >>= 1;
a = (a * a) % m;
}
return res % m;
}
void getshai() {
phi[1] = 1;
chk[1] = 1;
for (int i = 2; i <= MAXN; i++) {
if (!chk[i]) {
p[++tot] = i;
phi[i] = i - 1;
}
for (int j = 1; j <= tot && i * p[j] <= MAXN; j++) {
chk[i * p[j]] = 1;
if (i % p[j]) {
phi[i * p[j]] = phi[i] * phi[p[j]];
}
else {
phi[i * p[j]] = p[j] * phi[i];
break;
}
}
}
for (int i = 1; i <= MAXN; i++) {
pre2[i] = pre2[i - 1] + (ll)(phi[i] * i) % MOD;
pre2[i] %= MOD;
}
}
ll sum(ll a) {
return a * (a + 1) % MOD * (2 * a + 1) % MOD * kk % MOD;
}
ll getphi(ll x) {
if (x <= MAXN) return pre2[x];
if (ans2[x]) return ans2[x];
ll ans = sum(x);
for (re ll l = 2, r; l <= x; l = r + 1) {
r = x / (x / l);
ans -= 1LL * (r - l + 1LL) * (l + r) % MOD * tt % MOD * getphi(x / l);
ans += MOD;
ans %= MOD;
}
return ans2[x] = ans;
}
signed main() {
getshai();
scanf("%d", &n);
kk = qpow(6, MOD - 2, MOD);
tt = qpow(2, MOD - 2, MOD);
puts("1");
printf("%lld", getphi((ll)n));
}
|
