?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
216921242 |
Practice: BittersweetHerb |
653G - 16 | C++14 (GCC 6-32) | Accepted | 202 ms | 8228 KB | 2023-08-03 05:27:56 | 2023-08-03 05:27:56 |
#include<bits/stdc++.h> using namespace std; const int N=3e5+5,P=1e9+7; int n,fac[N],facinv[N],sum[N],F[N],cnt[N],flag[N],x[N],ans; int power(int a,int b){ int c=1; for(;b;b>>=1){ if(b&1)c=1ll*c*a%P; a=1ll*a*a%P; } return c; } int C(int n,int m){return 1ll*fac[n]*facinv[m]%P*facinv[n-m]%P;} void init(int n){ fac[0]=facinv[0]=1; for(int i=1;i<=n;i++){ fac[i]=1ll*fac[i-1]*i%P; facinv[i]=power(fac[i],P-2); } for(int i=1;i<=n;i++)sum[i]=(sum[i-1]+C(n-1,i-1))%P; for(int i=1;i<=n;i++)F[i]=(F[i-1]+0ll+sum[n]-sum[i]-sum[i-1]+2*P)%P; } int main(){ scanf("%d",&n);init(n); for(int i=1,x;i<=n;i++)scanf("%d",&x),++cnt[x]; for(int i=2;i<=N-5;i++)if(!flag[i]){ int h=0; for(int j=1;i*j<=N-5;j++){ flag[i*j]=1;int pwr=1,y=j; while(y%i==0)y/=i,++pwr; x[pwr]+=cnt[i*j];h=max(h,pwr); } for(int j=h,s=0;j>=1;j--) ans=(ans+F[s+=x[j]])%P,x[j]=0; } printf("%d\n",ans); return 0; }//14664150807335159478
?
?
?
?