J-Product of GCDs

Code1

對(duì)于每個(gè)質(zhì)數(shù)以及每個(gè)質(zhì)數(shù)的次冪單獨(dú)考慮他們的貢獻(xiàn)，由于多次使用快速冪導(dǎo)致TLE

#include<bits/stdc++.h> using namespace std; using ll=long long; template <class T=int> T rd() {T res=0;T fg=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') fg=-1;ch=getchar();}while( isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=getchar();return res*fg; }int prime[10000010],cnt,is[10000010]; void initP() {for(int i=2;i<=10000000;i++){if(!is[i]) prime[++cnt]=i;for(int j=1;prime[j]<=10000000/i;j++){is[prime[j]*i]=1;if(i%prime[j]==0) break;}} } int n,m; ll P,Phi; ll Cphi(ll v) {ll ans=v;for(int i=1;prime[i]<=v/prime[i];i++)if(v%prime[i]==0){ans=ans/prime[i]*(prime[i]-1);while(v%prime[i]==0) v/=prime[i];}if(v>1) ans=ans/v*(v-1);return ans; } const int N=8e4+10; ll C[N][35]; void mod(ll &v){if(v>=Phi) v-=Phi;} void initC() {for(int i=0;i<=n;i++){C[i][0]=1;for(int j=1;j<=min(i,m);j++){C[i][j]=C[i-1][j]+C[i-1][j-1],mod(C[i][j]);}} } ll mul(ll a,ll b){return(__int128)a*b%P;} ll qmi(ll a,ll b) {ll v=1;while(b){if(b&1) v=mul(v,a);b>>=1;a=mul(a,a);}return v; } int a[N]; int main() {initP();int Tc=rd();while(Tc--){n=rd(),m=rd(),P=rd<ll>(),Phi=Cphi(P);initC();for(int i=1;i<=n;i++) a[i]=rd();ll ans=1;for(int p=1;p<=8000;p++){static int b[N];for(int i=1;i<=n;i++) b[i]=0;for(int i=1;i<=n;i++) while(a[i]%prime[p]==0) a[i]/=prime[p],b[i]++;// 桶排序static int c[30];memset(c,0,sizeof c);int maxn=*max_element(b+1,b+1+n);if(maxn==0) continue;for(int i=1;i<=n;i++) c[b[i]]++;int cnt=0;for(int i=1;i<=maxn;i++) while(c[i]--) b[++cnt]=i;for(int i=1;i<=cnt;i++){ll pw=C[cnt-i][m-1];ans=mul(ans,qmi(qmi(prime[p],pw),b[i]));}}printf("%lld\n",ans);} }

Code2

考慮分質(zhì)因子統(tǒng)計(jì)，計(jì)算$f_{(p,c)}$表示至少包含 $p^c$ 的數(shù)個(gè)數(shù)，方案數(shù)為
$\left(\begin{array}{c}{f}_{(p,c)}\\ k\end{array}\right)$

注意需要計(jì)算得到的實(shí)際上是指數(shù)，因此我們需要對(duì)于𝜑(𝑷) 取模
（擴(kuò)展）歐拉定理學(xué)習(xí)筆記

好像很多同學(xué)關(guān)心加不加phi的問(wèn)題，，我發(fā)現(xiàn)歐拉降冪挺多題其實(shí)都沒(méi)故意卡這點(diǎn)也就是記住對(duì)𝜑(𝑷)取模即可~

通過(guò)分解質(zhì)因數(shù)暴力求𝜑(𝑷)即可，只需要預(yù)處理√𝑃 內(nèi)的質(zhì)數(shù)，復(fù)雜度為𝑂(√𝑃+𝑇 √𝑃/(𝑙𝑜𝑔 𝑃))
𝜑(𝑷)不是質(zhì)數(shù)，但是鑒于𝑘較小，組合數(shù)直接𝑂(𝑛𝑘)遞推即可（為此 𝑛 開(kāi)得比較小）

#include<bits/stdc++.h>using namespace std; using ll=long long; template <class T=int> T rd() {T res=0;char ch=getchar();while(!isdigit(ch)) ch=getchar();while( isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=getchar();return res; }int prime[10000010],cnt,is[10000010]; void initP() {for(int i=2;i<=10000000;i++){if(!is[i]) prime[++cnt]=i;for(int j=1;prime[j]<=10000000/i;j++){is[prime[j]*i]=1;if(i%prime[j]==0) break;}} } int n,m; ll P,Phi; ll Cphi(ll v) {ll ans=v;for(int i=1;prime[i]<=v/prime[i];i++)if(v%prime[i]==0){ans=ans/prime[i]*(prime[i]-1);while(v%prime[i]==0) v/=prime[i];}if(v>1) ans=ans/v*(v-1);return ans; } const int N=8e4+10; ll C[N][35]; void mod(ll &v){if(v>=Phi) v-=Phi;} void initC() {for(int i=0;i<=n;i++){C[i][0]=1;for(int j=1;j<=min(i,m);j++){C[i][j]=C[i-1][j]+C[i-1][j-1],mod(C[i][j]);}} } ll mul(ll a,ll b){return(__int128)a*b%P;} ll qmi(ll a,ll b) {ll v=1;while(b){if(b&1) v=mul(v,a);b>>=1;a=mul(a,a);}return v; } int a[N]; int main() {initP();int Tc=rd();while(Tc--){n=rd(),m=rd(),P=rd<ll>(),Phi=Cphi(P);initC();memset(a,0,sizeof a);for(int i=1;i<=n;i++) a[rd()]++;ll ans=1;for(int p=1;p<=8000;p++){ll res=0;for(int i=prime[p];i<N;i*=prime[p]){int c=0;for(int j=i;j<N;j+=i) c+=a[j];if(c<m) break;res+=C[c][m],mod(res);if(1ll*i*prime[p]>=N) break;}if(res) ans=mul(ans,qmi(prime[p],res));}printf("%lld\n",ans);} }

總結(jié)

以上是生活随笔為你收集整理的2021牛客暑期多校训练营2 J-Product of GCDs（数论+计数）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。