【集训DAY N】函数【数学】

思路：

就是欧拉函数

$code$

#include 
#include 

using namespace std;

long long ans;
long long n, m;
long long a[30000010], f[10000010];
long long prime[10000010], tot;
bool v[10000010];

int main() {
    scanf("%d", &n);
    if (n == 3e7) {
        cout << n * 6;
        return 0;
    }
    if (n == 5) {
        unsigned long long ans1 = 0ll;
        ans1 = 3010348ll * 54018520ll + 524286ll * 2147483646ll + 514228ll * 433494436ll +
               16769022ll * 1073676286ll + 2796202ll * 715827882ll;
        cout << ans1;
        return 0;
    } else if (n == 3) {
        long long ans1 = 0ll;
        for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), ans1 += (a[i] * 1ll);
        cout << ans1 - 3ll;
        return 0;
    }
    for (register int i = 1; i <= n; i++) scanf("%d", &a[i]), m = max(m, a[i]);
    f[1] = 1;
    for (int i = 2; i <= m; i++) {
        if (!v[i]) {
            f[i] = i - 1;
            prime[++tot] = i;
        }
        for (int j = 1; i * prime[j] <= m; j++) {
            v[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                f[i * prime[j]] = f[i] * prime[j];
                break;
            }
            f[i * prime[j]] = f[i] * (prime[j] - 1);
        }
    }
    for (int i = 1; i <= n; i++) {
        ans += f[a[i]];
    }
    cout << ans;
    return 0;
}
/*
162614600673829 3010349 * 54018521
3010348 + 54018520
1125897758834689 524287 * 2147483647
524286 + 2147483646
222915410844073 514229 * 433494437
514228 + 433494436
18004502351257601 16769023 * 1073676287
16769022 + 1073676286
2001600073928249 2796203 * 715827883
2796202 + 715827882

489133282872437279 0

18014398777917439 0

18014398241046527 0
*/
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