自动搬运

查看原文

来自洛谷，原作者为

	agicy 你很懒，什么都看不到

搬运于2025-08-24 21:52:26，当前版本为作者最后更新于2020-06-13 21:53:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

点此食用更佳：$\huge\texttt{My Blog}$。

$\texttt{Pollard Rho}$ 的简单题目。

题目链接：Luogu P3762/BZOJ 4891/TJOI2017 D2T2。

题目

题目描述

一句话题意：有长度为 $m$ 的正整数数列 $\{b _ m\},\{a _ m\} _ 1,\{a _ m\} _ 2,\cdots,\{a _ m\} _ n$，$k$ 次询问，每次给出 $x,M$，求：

$$(\dfrac{\prod^m _ {i=1}b _ i}{\prod^m _ {i=1}a _ {x,i}})^{-1}\pmod M $$

数据范围

变量	数据范围
$n$	$\leq 20$
$m$	$\leq 10000$
$k$	$\leq 50$
$M,a,b$	$\leq 2\times 10^{18}$

时空限制

题目编号	时间限制	空间限制
Luogu P3762	$1\to 5\text{s}$	$125\text{MiB}$
BZOJ 4891	$?\text{s}$	$?\text{MiB}$
TJOI2017 D2T2	$1\to 5\text{s}$	$128\text{MiB}$

题解

思路

直接乘显然是不行的，那么我们考虑上下分解质因子、约分后再求值。

但是考虑最快的质因子分解算法 $\texttt{Pollard Rho}$，这样做的单次询问的时间复杂度都为 $O(m\times\max\{M,a,b\}^\frac{1}{4})$，显然过不掉。

我们不妨换一种思路，考虑分解模数 $M$，那么我们就可以将所有的 $a,b$ 提前约掉 $M$ 的质因子，剩余部分与 $M$ 显然互质，就可以直接求逆元了。

注意，如果分解后得出某个质因子有负数次方，那么显然无解。

最后求逆元记得用欧拉定理而不是费马小定理求逆元。

这种做法的时间复杂度为 $\Theta(k(M^\frac{1}{4}+m+\log _ 2\varphi(M)))$

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline ll read(void){
	reg char ch=getchar();
	reg ll res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXN=20+5;
const int MAXM=10000+5;

int n,m,K;
ll b[MAXM];
ll a[MAXN][MAXM];

inline ll add(reg ll a,reg ll b,reg ll mod){
	reg ll sum=a+b;
	return sum>=mod?sum-mod:sum;
}

inline ll mul(reg ll a,reg ll b,reg ll mod){
	reg ll res=0;
	while(b){
		if(b&1)
			res=add(res,a,mod);
		a=add(a,a,mod);
		b>>=1;
	}
	return res;
}

inline ll pow(reg ll x,reg ll exp,reg ll mod){
	reg ll res=1;
	while(exp){
		if(exp&1)
			res=mul(res,x,mod);
		x=mul(x,x,mod);
		exp>>=1;
	}
	return res;
}


const int MAXSIZE=10000+5;

inline bool Miller_Rabin(reg ll n){
	if(n==2)
		return true;
	const int TEST_TIME=10;
	for(reg int i=TEST_TIME;i;--i){
		reg ll a=rand()%(n-2)+1;
		reg ll p=n-1;
		if(pow(a,n-1,n)!=1)
			return false;
		while(!(p&1)){
			p>>=1;
			reg ll temp=pow(a,p,n);
			if(mul(temp,temp,n)==1&&temp!=1&&temp!=n-1)
				return false;
		}
	}
	return true;
}

inline ll gcd(reg ll a,reg ll b){
	return b==0?a:gcd(b,a%b);
}

inline ll Pollard_Rho(reg ll n){
	reg ll i=0,k=2,x=rand()%(n-1)+1,y=x;
	reg int c=rand();
	while(true){
		++i;x=(mul(x,x,n)+c)%n;
		reg ll Gcd=gcd((y-x+n)%n,n);
		if(Gcd!=1&&Gcd!=n)
			return Gcd;
		if(x==y)
			return n;
		if(i==k)
			k<<=1,y=x;
	}
	return n;
}

int tot;
ll fac[MAXSIZE],T[MAXSIZE];

inline void Div(reg ll n){
	if(n==1)
		return;
	if(Miller_Rabin(n)){
		fac[++tot]=n;
		return;
	}
	reg ll p=n;
	while(p>=n)
		p=Pollard_Rho(n);
	Div(p),Div(n/p);
	return;
}

ll ta[MAXM];
ll tb[MAXM];

inline void Solve(reg int id,reg ll M){
	tot=0;
	memset(T,0,sizeof(T));

	Div(M);
	sort(fac+1,fac+tot+1);
	tot=unique(fac+1,fac+tot+1)-(fac+1);

	reg ll phi=M;
	for(reg int i=1;i<=tot;++i)
		phi=phi/fac[i]*(fac[i]-1);

	for(reg int i=1;i<=m;++i){
		tb[i]=b[i];
		for(reg int j=1;j<=tot;++j)
			if(tb[i]%fac[j]==0)
				while(tb[i]%fac[j]==0){
					++T[j];
					tb[i]/=fac[j];
				}
	}
	for(reg int i=1;i<=m;++i){
		ta[i]=a[id][i];
		for(reg int j=1;j<=tot;++j)
			if(ta[i]%fac[j]==0)
				while(ta[i]%fac[j]==0){
					--T[j];
					ta[i]/=fac[j];
				}
	}
	reg ll ans1=1,ans2=1;
	for(reg int i=1;i<=tot;++i)
		if(T[i]<0){
			puts("-1");
			return;
		}
		else if(T[i])
			ans1=mul(ans1,pow(fac[i],T[i],M),M);
	for(reg int i=1;i<=m;++i)
		ans1=mul(ans1,tb[i],M),ans2=mul(ans2,ta[i],M);
	printf("%lld\n",mul(ans1,pow(ans2,phi-1,M),M));
	return;
}

int main(void){
	srand(time(0));
	n=read(),m=read(),K=read();
	for(reg int i=1;i<=m;++i)
		b[i]=read();
	for(reg int i=1;i<=n;++i)
		for(reg int j=1;j<=m;++j)
			a[i][j]=read();
	for(reg int i=1;i<=K;++i){
		static ll x,M;
		x=read(),M=read();
		Solve(x,M);
	}
	return 0;
}