水题笔记_ SDOI2008 仪仗队 [欧拉函数]

暴力可以给人灵感的火花

关于欧拉函数

欧拉函数, $\phi(i)$表示小于等于 $i$ 且与 $i$ 互质的数的个数
$\phi(i) = \prod (p_i - 1) \cdot (p_i ^{ (k_i - 1)}) = x \cdot \prod (p_i - 1) / p_i$

懵逼的 题目

传送至 BZOJ

扯淡的 题解

看到这题第一反应就是n ^ 2求每个点的 tan值, 然后排序去重…
30
然后发现是不是可以把横纵坐标取个GCD除一下, 把最简比去重就好了…
然后又发现这不就是要求横纵坐标互质嘛…
不就是对每一个横坐标求与他互质的比他小的数的个数嘛…
这不就是欧拉函数嘛…
好了, 剩下的都不会了
然后就是各种翻欧拉函数的板子…
理解证明什么的…背过就好了…反正又不像数竞考证明
然后…
WAWAWA

写欧拉筛都写不对我怕不是药丸

沙茶的 代码

30分大暴力(我跟你讲我暴力都错过2次)

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (10000 + 5)
#define DD double
using namespace std;
int n;
DD a[MAXN * MAXN];
int main()
{
scanf("%d", &n);
int cnta = 1;
for (int i = 0; i < n; i++)
{
for (int j = 1; j < n; j++)
{
a[cnta++] = (DD) ((DD)i / j);
}
}
sort(a + 1, a + cnta + 1);
int ans = unique(a + 1, a + cnta + 1) - a - 1 + 1;
printf("%d", ans);
return 0;
}

AC, 求单个phi

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN (400000 + 5)
using namespace std;
int n;
int ans;
int phi(int);
int main()
{
scanf("%d", &n);
for (int i = 2; i < n; i++)
{
ans += phi(i);
}
ans = (ans << 1) + 3;
printf("%d", ans);
return 0;
}
int phi(int x)
{
int re = x;
for (int i = 2; i * i <= x; i++)
{
if (x % i == 0)
{
re /= i;
re *= (i - 1);
while (x % i == 0)
{
x /= i;
}
}
}
if (x > 1)
{
re = re / x * (x - 1);
}
return re;
}

AC, 求phi(1 ~ n), 所以也就是说如果不爆LL数据还能大

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
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define MAXN (40000 + 5)
using namespace std;
int n;
int p[MAXN];
int cntp;
bool is_p[MAXN];
int eul[MAXN];
long long ans;
void init();
void euler();
int main()
{
scanf("%d", &n);
init();
euler();
for (int i = 2; i <= n - 1; i++)
{
ans += eul[i];
// cout << eul[i] << " ";
}
ans = (ans << 1) + 3;
printf("%d", ans);
return 0;
}
void init()
{
for (int i = 1; i <= n; i++)
{
eul[i] = i;
}
memset(is_p, false, sizeof(is_p));
for (int i = 2; i <= n; i++)
{
if (!is_p[i])
{
p[++cntp] = i;
}
for (int j = 1; j <= cntp && p[j] * i <= n; j++)
{
is_p[i * p[j]] = true;
if (i % p[j] == 0)
{
break;
}
}
}
}
void euler()
{
for (int i = 1; i <= cntp && p[i] <= n; i++)
{
for (int j = p[i]; j <= n; j += p[i])
{
eul[j] /= p[i];
eul[j] *= (p[i] - 1);
}
}
}

By 神经病的 Cansult