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

时间：2022-07-22 16:48:11

上三角行恰好是[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 ;

 }

相关文章