https://www.cnblogs.com/zwfymqz/p/9332753.html
由于欧拉函数是积性函数,可以用乘法分配律变成对每个质因子分开算最后乘起来。再由欧拉函数公式和分配律发现就是等比数列求和问题,特判下1的问题就好了。
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef long long ll;
using namespace std; const int mod=1e9+;
int n,x,cnt,tot,ans=,sm[],p[],b[];
struct P{ int x,y; }a[];
bool cmp(const P &a,const P &b){ return a.x<b.x || (a.x==b.x && a.y<b.y); } int ksm(int a,int b){
int res=;
for (; b; a=1ll*a*a%mod,b>>=)
if (b & ) res=1ll*res*a%mod;
return res;
} void Fac(int x){
for (int i=; p[i]*p[i]<=x; i++)
if (x%p[i]==){
int s=;
while (x%p[i]==) x/=p[i],s++;
a[++cnt]=(P){p[i],s};
}
if (x>) a[++cnt]=(P){x,};
} void init(int n){
rep(i,,n){
if (!b[i]) p[++tot]=i;
for (int j=; j<=tot && i*p[j]<=n; j++){
b[i*p[j]]=;
if (i%p[j]==) break;
}
}
} int main(){
freopen("bzoj3560.in","r",stdin);
freopen("bzoj3560.out","w",stdout);
scanf("%d",&n); init();
rep(i,,n) scanf("%d",&x),Fac(x);
sort(a+,a+cnt+,cmp);
for (int i=,j; i<=cnt; i=j+){
for (j=i; j<cnt && a[j+].x==a[j].x; j++);
sm[]=; int tmp=;
rep(k,,a[j].y) sm[k]=1ll*sm[k-]*a[i].x%mod;
rep(k,,a[j].y) sm[k]=(sm[k-]+sm[k])%mod;
rep(k,i,j) tmp=1ll*tmp*sm[a[k].y]%mod;
tmp=1ll*(tmp-)*(a[i].x-)%mod*ksm(a[i].x,mod-)%mod+;
ans=1ll*ans*tmp%mod;
}
printf("%d\n",ans);
return ;
}