【BZOJ4891】[TJOI2017]龙舟（Pollard_rho）

时间：2022-07-29 08:18:37

【BZOJ4891】[TJOI2017]龙舟（Pollard_rho）

题面

BZOJ

洛谷

题解

看了半天题....就是让你求\(\frac{b}{a}\)在模\(M\)意义下的值。。。

首先把\(M\)分解，把\(a,b\)中的这些质因子全部分解出来，剩下的部分和\(M\)互质，直接求逆就行了，分解出来的部分如果分母大于分子，显然无逆，输出-1就行了。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

inline ll read()

{

	ll x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

ll Multi(ll x,ll y,ll MOD){ll s=x*y-(ll)((long double)x/MOD*y+0.5)*MOD;return s<0?s+MOD:s;}

ll fpow(ll a,ll b,ll MOD){ll s=1;while(b){if(b&1)s=Multi(s,a,MOD);a=Multi(a,a,MOD);b>>=1;}return s;}

bool Miller_Rabin(ll n)

{

	if(n==2)return true;

	for(int tim=10;tim;--tim)

	{

		ll a=rand()%(n-2)+2,p=n-1;

		if(fpow(a,n-1,n)!=1)return false;

		while(!(p&1))

		{

			p>>=1;ll nw=fpow(a,p,n);

			if(Multi(nw,nw,n)==1&&nw!=1&&nw!=n-1)return false;

		}

	}

	return true;

}

ll Pollard_Rho(ll n,int c)

{

	ll i=0,k=2,x=rand()%(n-1)+1,y=x;

	while(233)

	{

		++i;x=(Multi(x,x,n)+c)%n;

		ll d=__gcd((y-x+n)%n,n);

		if(d!=1&&d!=n)return d;

		if(x==y)return n;

		if(i==k)k<<=1,y=x;

	}

}

void Fact(ll n,int c,vector<ll> &fac)

{

	if(n==1)return;

	if(Miller_Rabin(n)){fac.push_back(n);return;}

	ll p=n;while(p>=n)p=Pollard_Rho(n,c--);

	Fact(p,c,fac);Fact(n/p,c,fac);

}

int n,m,Q;ll a[25][10100];

int pri[100];

int main()

{

	n=read();m=read();Q=read();

	for(int i=0;i<=n;++i)

		for(int j=1;j<=m;++j)a[i][j]=read();

	while(Q--)

	{

		int x=read();ll MOD=read(),phi=MOD;int tot;

		vector<ll> fac;Fact(MOD,233,fac);

		sort(fac.begin(),fac.end());fac.resize(tot=unique(fac.begin(),fac.end())-fac.begin());

		for(int i=0;i<tot;++i)phi=phi-phi/fac[i];

		ll inv=1,ans=1;

		for(int i=1;i<=m;++i)

		{

			ll p=a[0][i];

			for(int j=0;j<tot;++j)

				while(p%fac[j]==0)p/=fac[j],++pri[j];

			ans=Multi(ans,p,MOD);

		}

		for(int i=1;i<=m;++i)

		{

			ll p=a[x][i];

			for(int j=0;j<tot;++j)

				while(p%fac[j]==0)p/=fac[j],--pri[j];

			inv=Multi(inv,p,MOD);

		}

		bool fl=true;

		for(int i=0;i<tot;++i)if(pri[i]<0){fl=false;break;}

		if(fl)

		{

			for(int i=0;i<tot;++i)if(pri[i])ans=Multi(ans,fpow(fac[i],pri[i],MOD),MOD);

			ans=Multi(ans,fpow(inv,phi-1,MOD),MOD);printf("%lld\n",ans);

		}

		else puts("-1");

		for(int i=0;i<tot;++i)pri[i]=0;

	}

	return 0;

}

相关文章