?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
257524251 |
Practice: Traverser_Steal69 |
653G - 16 | C++14 (GCC 6-32) | Accepted | 780 ms | 13736 KB | 2024-04-21 10:28:40 | 2024-04-21 10:28:40 |
#include<bits/stdc++.h> using namespace std;typedef long long ll;const int MAX=3e5+9,MOD=1e9+7;vector<int>g[MAX];ll ans,fact[MAX],inv[MAX],mul[MAX],n;ll pw(ll a,ll b){return b?pw(a*a%MOD,b>>1)*(b&1?a:1)%MOD:1;}ll c(ll n,ll r){return fact[n]*inv[r]%MOD*inv[n-r]%MOD;}int main(){fact[0]=inv[0]=1;for(int i=1;i<MAX;i++)fact[i]=fact[i-1]*i%MOD,inv[i]=pw(fact[i],MOD-2);cin>>n;for(int i=0,x;i<n;i++){cin>>x;for(int j=2;j*j<=x;j++)if(x%j==0){int t=0;while(x%j==0)t++,x/=j;g[j].push_back(t);}if(x>1)g[x].push_back(1);}mul[0]=(pw(2,n-1)-1+MOD)%MOD;for(int i=1;i<n;i++)mul[i]=((mul[i-1]-c(n-1,i)-c(n-1,i-1))%MOD+MOD)%MOD;for(int i=1;i<MAX;i++){sort(g[i].begin(),g[i].end(),greater<int>());for(int j=0;j<g[i].size();j++)ans=(ans+g[i][j]*mul[j])%MOD;}cout<<ans;}
?
?
?
?