https://www.luogu.org/problem/show?pid=3200
首先，我們不能保證要求的數(shù)的逆元和模域互質(zhì)；
所以我們要用分解質(zhì)因數(shù)來(lái)抵消除法；
其實(shí)逆元的話即使可行也會(huì)超時(shí)；
那么我轉(zhuǎn)載了，實(shí)在沒(méi)什么可以說(shuō)的；
另外卡特蘭數(shù)
http://baike.baidu.com/link?url=St3mmth0khr1jUoD9Vwdroupnfajo6hhTSgwvOkjAPrP0Htt12nZjsMue4T_5JhMopRqlhgAkCt2dDzd378Kg8xjsSYwGn3J_CMLgsvI4Psdhj3z0s4zTucxc1v6dRlP
話說(shuō)這個(gè)方法好巧妙啊
http://blog.csdn.net/jiangshibiao/article/details/24009239
【轉(zhuǎn)化】就是求卡特蘭數(shù)。
【初始代碼】

#include<cstdio> using namespace std; typedef long long ll; ll prime[200005],a[200005]; bool f[2000005]; ll temp,n,p,i,j,cnt,mod; ll pow(ll a,ll b) { ll ans; for (ans=1;b;b>>=1,a=a*a%mod) if (b&1) ans=ans*a%mod; return ans; } int main() { scanf("%lld%lld",&n,&mod); for (i=2;i<=n*2;i++) { if (!f[i]) prime[++cnt]=i; for (j=1;j<=cnt&&prime[j]*i<=n*2;j++) f[prime[j]*i]=true; } for (i=n+2;i<=n*2;i++) for (j=1,p=i;j<=cnt&&p;j++) while (p%prime[j]==0) a[j]++,p/=prime[j]; for (i=2;i<=n;i++) for (j=1,p=i;j<=cnt&&p;j++) while (p%prime[j]==0) a[j]--,p/=prime[j]; temp=1; for (j=1;j<=cnt;j++) if (a[j]) temp=(temp*pow(prime[j],a[j]))%mod; printf("%lld",temp);for (;;); return 0; }

用歐拉篩法，O（n）的效率求出每個(gè)質(zhì)數(shù)。然后枚舉階乘，像質(zhì)數(shù)表一樣把一個(gè)數(shù)給分解。但是效率很低。
【優(yōu)化1】如果一個(gè)數(shù)是合數(shù)，我們可以把它的某個(gè)因子記下來(lái)。然后我們同樣從開(kāi)始枚舉階乘，而且是倒著枚舉。對(duì)于每個(gè)數(shù)，如果它是合數(shù)，我就把它分解。比如，設(shè)f[n]為結(jié)果中含有n因子的個(gè)數(shù)。u是n的一個(gè)約數(shù)。那么我們可以f[u]+=f[n],f[n/u]+=f[n]。這樣就不用多次用快速冪了。直到n是質(zhì)數(shù)為止。
【優(yōu)化2】開(kāi)始可以把1–n的f[i]設(shè)為-1，把n+2–2*n(注意，最后要除n+1,所以從n+2開(kāi)始)的f[i]設(shè)為1.這樣只需1次循環(huán)。
【AC代碼】

#include<cstdio> using namespace std; typedef long long ll; ll prime[200005],a[2000005],come[2000005]; ll temp,n,p,i,j,cnt,mod; ll pow(ll a,ll b) { ll ans; for (ans=1;b;b=b/2,a=a*a%mod) if (b&1) ans=ans*a%mod; return ans; } int main() { scanf("%lld%lld",&n,&mod); for (i=2;i<=n*2;i++) { if (!come[i]) prime[++cnt]=i; for (j=1;j<=cnt&&prime[j]*i<=n*2;j++) come[prime[j]*i]=i; } temp=1; for (i=2;i<=n;i++) a[i]=-1; for (i=n+2;i<=2*n;i++) a[i]=1; for (i=n*2;i>1;i--) if (come[i]) { a[come[i]]+=a[i]; a[i/come[i]]+=a[i]; } else temp=temp*pow(i,a[i])%mod; printf("%lld",temp); return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/largecube233/p/6797912.html

總結(jié)

以上是生活随笔為你收集整理的分解质因数-洛谷P3200 [HNOI2009]有趣的数列的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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