有这么一个函数满足Σf(d)=n (d|n)，给出序列a，求Σf(a[i])

首先，大部分人一眼就能看出这个f就是phi吧

那么考虑怎么求

有

phi(p)=p-1(p为质数)

phi(ab)=phi(a)phi(b)(gcd(a,b)=1)

phi(ka)=kphi(a)(k|a且k为质数)

那么我们就可以类似于素数筛法的来计算phi了

（这道题有三个点是题答题，还有一个点数据错了。。。）

#include
    
     #include
     
      #include
      
       using namespace std;bool vis[10000010];int phi[10000010],w[1000010],t=0,n;int main(){	scanf("%d",&n); phi[1]=1;	for(int i=2;i<=10000000;++i){		if(!vis[i]){ phi[i]=i-1; w[t++]=i; }		for(int j=0;j
       
        <=10000000;++j){			vis[i*w[j]]=1;			if(i%w[j]) phi[i*w[j]]=phi[i]*(w[j]-1);			else{ phi[i*w[j]]=phi[i]*w[j]; break; }		}	}	if(n==30000000) return 0&puts("180000000");	if(n==3){ long long a,b,c;		scanf("%lld%lld%lld",&a,&b,&c);		return 0&printf("%lld\n",a+b+c-3);	}	if(n==5){ long long x,S=0;		for(;n--;){			scanf("%lld",&x);			for(int i=0;i