P2158 [SDOI2008]仪仗队 线性筛(欧拉函数和素数表)

上三角行恰好是[1,n-1]的欧拉函数

http://www.luogu.org/problem/show?pid=2158#sub

 //#pragma comment(linker, "/STACK:167772160")
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <utility>
#include <algorithm>
#include <vector>
#include <map>
// #include<malloc.h>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define LL long long
void fre() {
freopen("in.txt","r",stdin);
}
const int inf = 0x3f3f3f3f;
#define eps 1e-8
// const double pi = acos(-1);
const LL mod = 1e9+;
inline int r(){
int x=,f=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
const int maxn=1e7;
const int N=;
bool vis[maxn];
int phi[maxn];
int prime[maxn];
int tot;
void p_pri(){
// clc(vis,0);
phi[]=;
tot=;
int i,j;
for(i=;i<=N;i++){
if(!vis[i]){
prime[tot++]=i;
phi[i]=i-;
}
for(j=;j<tot;j++){
if(i*prime[j]>N) break;
vis[i*prime[j]]=true;
if(i%prime[j]==){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else{
phi[i*prime[j]]=phi[i]*(prime[j]-);
}
}
}
} int main(){
int n;
LL ans;
ans=;
scanf("%d",&n);
p_pri();
for(int i=;i<n;i++){
ans+=phi[i];
}
cout<<ans*+<<endl;
return ;
}
上一篇:pscp实现Windows 和Linux 文件互相传输


下一篇:python3倒叙字符串