poj 2478(欧拉函数)

poj 2478
筛选法求欧拉函数

每个询问答案是$$\sum_{i=1}^n\varphi(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
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ms(i,j) memset(i,j, sizeof i);
using namespace std;
#define ll long long
ll phi[1000000+5];
void phitable(ll n)
{
for (int i=2;i<=n;i++) phi[i] = 0;
phi[1] = 1;
for (int i=2;i<=n;i++) if (!phi[i])
for (int j=i;j<=n;j+=i)
{
if (!phi[j]) phi[j] = j;
phi[j] = phi[j]/i*(i-1);
}
}
int main()
{
phitable(1000000);
int n;
while (scanf("%d", &n)==1 && n)
{
ll tot = 0;
for (int i=2;i<=n;i++) tot += phi[i];
printf("%lld\n", tot);
}
return 0;
}

------ 本文结束 ------