P2158 [SDOI2008] 仪仗队（欧拉函数模板）

题目描述

作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 现在，C君希望你告诉他队伍整齐时能看到的学生人数。

分析就不写了都写得很《《《《全》》》》了
就当看模板叭

#include<iostream>

#include<cstdio>

using namespace std;

typedef long long ll;

int rd(){

    ll x=,fl=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')fl=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=(x<<)+(x<<)+(ch^);ch=getchar();}

    return x*fl;

}

int n,ans,cnt,pri[],ex[],phi[];

/*ola打表*/

void ola(){

    ex[]=ex[]=;cnt=;

    for(int i=;i<=n;i++){

        if(!ex[i]){

            pri[++cnt]=i;//如果是素数的话，它的欧拉函数就等于他自己-1

            phi[i]=i-;

        }

        for(int j=;j<=cnt&&pri[j]*i<=n;j++){

            ex[pri[j]*i]=;

            if(i%pri[j])phi[i*pri[j]]=phi[i]*(pri[j]-);//下面是不是素数的情况下分两种情况讨论的递推公式

            else{

                phi[i*pri[j]]=phi[i]*pri[j];

                break;

            }

        }

    }

}

int ola2(int n){

    if(n==)return ;

    int ans=n,k=;

    for(int i=;n!=;i+=k)

        if(!(n%i)){

            ans/=i;ans*=(i-);

            while(!(n%i))

                n/=i;

            i=k;

        }

    return ans;

}

int main(){

    n=rd();

    ola();

    for(int i=;i<n;i++)

        ans+=phi[i];

//    for(int i=2;i<n;i++)

    //    ans+=ola2(i);  //   另一种做法（好慢。。

    printf("%d",ans*+);

    return ;

}