法理序列Fn是指对于任意整数n( n >= 2)，由不可约的分数a/b（0 < a < b <= n），gcd(a,b) = 1升序排列构成的序列，最开始的几个如下
F2 = {1/2}
F3 = {1/3, 1/2, 2/3}
F4 = {1/4, 1/3, 1/2, 2/3, 3/4}
F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}
你的任务是计算法理序列Fn中的元素个数。
解题思路
裸的欧拉函数。
欧拉函数：对于一个正整数n，小于n且和n互质的正整数（包括1 ）的个数，记做φ(n) 。
通式：φ(x)=x×(1−1/p1)×(1−1/p2)×(1−1/p3)×(1−1/p4)…..(1−1/pn),其中p1,p2,···,pn为x的所有质因子（不包括1，1不是质数），x是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）。
直接用埃氏筛，枚举到质数时，对于每个他的倍数，乘上\Large \frac{p_i - 1}{p_i}即可。
但是每输入一遍就跑一遍会超时，所以可以提前跑一遍最大值，然后前缀和，输出答案即可。
完整代码
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
87
88
89
| #include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
#define rep(i,a,n) for (ll i=a;i<=n;i++)
#define per(i,a,n) for (ll i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define bg begin
#define rbg rbegin
#define ed end
#define dbg(x) cout << #x << "===" << x << endl
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e6 + 5;
int cnt;
long long prime[N], les[N];
bool vis[N];
int gcd(int a, int b) {
return !b ? a : gcd(b, a % b);
}
ll qpow(ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) ans *= a;
a <<= 1, b >>= 1;
}
return ans;
}
void init(ll maxn) {
cnt = 0;
for (ll i = 2; i <= maxn; i++) {
if (!vis[i]) {
for (ll j = 2; i * j <= maxn; j++) {
vis[i * j] = 1;
if (!les[i * j]) les[i * j] = i * j;
les[i * j] = les[i * j] / i * (i - 1);
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n;
init(N - 5);
for (int i = 2; i <= N - 5; i++) {
if(les[i]) les[i] = i - 1 - les[i];
les[i] += les[i - 1];
}
while (cin >> n && n) {
ll ans = n * (n - 1) / 2;
ans -= les[n];
cout << ans << endl;
}
return 0;
}
|
