首页 > 代码库 > 【bzoj1951】 Sdoi2010—古代猪文

【bzoj1951】 Sdoi2010—古代猪文

2024-08-15 05:10:21   209人阅读

http://www.lydsy.com/JudgeOnline/problem.php?id=1951 (题目链接)

题意

　　废话一堆。。求解：

技术分享

Solution

　　真的是数论经典题，什么都用上了。

　　因为费马小定理，每p-1个g相乘会得到1，那么容易得到： 

技术分享

　　所以现在关键是求：

　　技术分享

　　大组合数取模，Lucas定理，可是p-1并不是一个质数，怎么办呢。我们考虑用中国剩余定理，先将p-1质因数分解，再分别在模各个质因子的的条件下求出余数，最后用中国剩余定理合并得解。

代码

// bzoj1951#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<queue>#define P 999911659#define inf 2147483640#define LL long long#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);using namespace std;int t[4]={2,3,4679,35617};int n,g,r[4],fac[4][100010];int power(LL a,int b,LL c) {	a%=c;	LL res=1;	while (b) {		if (b&1) res=res*a%c;		b>>=1;a=a*a%c;	}	return res;}int C(int n,int m,int p) {	if (m<n) return 0;	return (LL)(fac[p][m]*power((LL)fac[p][n]*fac[p][m-n],t[p]-2,t[p]))%t[p];}int Lucas(int n,int m,int p) {	if (m==0) return 1;	return C(n%t[p],m%t[p],p)*Lucas(n/t[p],m/t[p],p)%t[p];}void exgcd(int a,int b,LL &x,LL &y) {	if (b==0) {x=1,y=0;return;}	exgcd(b,a%b,y,x);	y-=a/b*x;}int CRT() {	LL x,y,M=t[0],R=r[0];	for (int i=1;i<4;i++) {		int mm=t[i],rr=r[i];		exgcd(M,mm,x,y);		x=((rr-R)*x%mm+mm)%mm;		R+=M*x;		M*=mm;	}	return R;}int main() {	free("aaa");	scanf("%d%d",&n,&g);	if (g==P) {printf("0");return 0;}	for (int i=0;i<4;i++) {		fac[i][0]=1;		for (int j=1;j<=t[i];j++)			fac[i][j]=fac[i][j-1]*j%t[i];	}	for (int i=0;i<4;i++)		for (int j=1;j*j<=n;j++) if (n%j==0) {				r[i]=(r[i]+Lucas(j,n,i))%t[i];				if (j*j!=n) r[i]=(r[i]+Lucas(n/j,n,i))%t[i];			}	printf("%d",power(g,CRT(),P));	fclose(stdin);fclose(stdout);	return 0;}

　　

【bzoj1951】 Sdoi2010—古代猪文


联系
我们