bzoj1485 [HNOI2009]有趣的数列

本文主要是介绍bzoj1485 [HNOI2009]有趣的数列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：bzoj1485

虽然有点很难看，但是我也没有办法，csdn吞我题解啊。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
#define maxn 500010
#define N 2001000bool is[N];int cnt;
int mod,n,num[maxn],pri[maxn],mpr[N];
void get_prime()
{int i,j;cnt=0;for (i=2;i<=2*n;i++){if (!is[i]) {pri[++cnt]=i;mpr[i]=cnt;}for (j=1;pri[j]*i<=2*n && j<=cnt;j++){mpr[pri[j]*i]=j;is[pri[j]*i]=true;if (i%pri[j]==0) break;}}
}
void sw(int x,int t)
{while (x!=1){num[mpr[x]]+=t;x/=pri[mpr[x]];}
}
int qpow(int x,int t)
{int ret=1;while (t){if (t&1) ret=(ret*x)%mod;x=(x*x)%mod;t>>=1;}return ret;
}
int main()
{//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);scanf("%d%d",&n,&mod);LL ans=1;get_prime();for (int i=1;i<=cnt;i++) num[i]=0;for (int i=2*n;i>n;i--) sw(i,1);for (int i=2;i<=n+1;i++) sw(i,-1);for (int i=1;i<=cnt;i++) ans=(ans*qpow(pri[i],num[i]))%mod;printf("%lld\n",ans);return 0;
}

这篇关于bzoj1485 [HNOI2009]有趣的数列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---