线性&&单个 欧拉函数

``` //线性筛 const int N=1e5+100; int v[N],phi[N],prime[N]; void pre(){ phi[1]=1; for(int i=2;i<=n;i++){ if(!v[i]){ v[i]=i; phi[i]=i-1; prime[++cnt]=i; } for(int j=1;j<=cnt;j++){ int t=prime[j]; if(t*i>n||t>v[i])break; v[i*t]=t; if(i%t==0)phi[i*t]=phi[i]*t; else phi[i*t]=phi[i]*(t-1); } } } //求单个 int euler(int x){ int ans=x; for(int j=2;j<=sqrt(x);j++){ if(x%j==0){ ans=ans/i*(i-1); while(x%j==0)x/=j; } } if(x>0)ans=ans/x*(x-1); return ans; } ```