欧拉筛+phi
wenge
2020-08-04 05:45:13
```cpp
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define clr(a,b) memset(a,b,sizeof(a))
#define PRINT(x) cout<<#x<<" = "<<x
#define br cout<<"\n"
#define N 200005
ll n,q,m,ans;
ll vis[10000005],prime[1000005],phi[10000005];
int main(){
//freopen("P1429_6.in","r",stdin);
//freopen("match.out","w",stdout);
//ios::sync_with_stdio(false);
//cin.tie(0);
cin>>n;
vis[1]=phi[1]=1;
for(int i=2;i<=n;i++){
if(!vis[i]){
prime[++m]=i;
phi[i]=i-1;
}
for(int j=1;j<=m&&i*prime[j]<=n;j++){
vis[i*prime[j]]=1;
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else{
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
}
cout<<ans;
return 0;
}
```