• 周五. 12月 9th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

【poj2478】Farey Sequence

admin

11月 28, 2021

题意:

求前n项的欧拉函数之和

题解:

预处理出所有欧拉函数 赤裸裸的模版题- – 没什么好说的

代码:

 1 #include <cstdio>
 2 typedef long long ll;
 3 const ll N=1000001;
 4 ll n,phi[N],pri[N],bo[N];
 5 void makepri(){
 6     for (ll i=2;i<=N;i++){
 7         if (!bo[i]){
 8             pri[++pri[0]]=i;
 9             phi[i]=i-1;
10         }
11         for (ll j=1;j<=pri[0] && i*pri[j]<=N;j++){
12             bo[i*pri[j]]=1;
13             if (i%pri[j]) phi[i*pri[j]]=phi[i]*(pri[j]-1);
14             else{
15                 phi[i*pri[j]]=phi[i]*pri[j];
16                 break;
17             }
18         }
19     }
20 }
21 int main(){
22     makepri();
23     for (ll i=1;i<=N;i++) phi[i]+=phi[i-1];
24     while (scanf("%I64d",&n),n) printf("%I64d
",phi[n]);
25 }

View Code

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注