C++14(g++5.4) 解法, 执行用时: 494ms, 内存消耗: 5980K, 提交时间: 2020-09-25 17:04:34

#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N = 1e4 + 2;
ll p[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
ll A[21][N], B[N], aa[N], bb[N], fac[N], prifac[N];
ll qp(ll a,ll x,ll mod){
	ll i = 1;
	for(;x; x >>= 1, a = (__int128)a * a % mod)if(x & 1)i = (__int128)i * a % mod;
	return i;
}
ll gcd(ll a,ll b){
	ll r;
	while(b)r = a % b, a = b, b = r;
	return a;
}
bool isPrime(ll n){
	ll i, x = n - 1, a, y, j, z;
	if(n == 2)return 1;
	if(n <= 1 || (n & 1 ^ 1))return 0;
	for(a = 0;x & 1 ^ 1;a++, x >>= 1);
	for(i = 0;i < 10 && p[i] < n;i++){
		y = qp(p[i], x, n);
		for(j = 0;j < a;j++, y = z){
			z = (__int128)y * y % n;
			if(z == 1 && y != 1 && y != n - 1)return 0;
		}if(y != 1)return 0;
	}
	return 1;
}
ll getfac(ll n, ll c){
	ll d, x = 1ll * rand() * rand() % (n - 1) + 1, y = x, k = 1, i, s = 1;
	for(i = d = 1; d == 1;i++){
		x = ((__int128)x * x % n + c) % n;
		s = (__int128)s * abs(x - y) % n;
		if(x == y || !s)return n;
		d = gcd(s, n);
		if(i == k){
			d = gcd(s, n);
			y = x;k <<= 1;
		}
	}return d;
}
void rho(ll n){
	if(n <= 1)return;
	if(isPrime(n)){
		prifac[++prifac[0]] = n;
		return;
	}ll t = n;
	while(t == n)t = getfac(n, 1ll * rand() * rand() % n + 1);
	while(!(n % t))n /= t;
	rho(t);rho(n);
}
int main(){
	ll n, m, T, i, j, mod, k, phi;
	scanf("%lld%lld%lld", &n, &m, &T);
	for(i = 1;i <= m;i++)scanf("%lld", &B[i]);
	for(i = 1;i <= n;i++)for(j = 1;j <= m;j++)scanf("%lld", &A[i][j]);
	while(T--){
		scanf("%lld%lld", &n, &mod);
		prifac[0] = 0;rho(mod);
		sort(prifac + 1, prifac + prifac[0] + 1);
		prifac[0] = unique(prifac + 1, prifac + prifac[0] + 1) - prifac - 1;
		for(i = 1;i <= prifac[0];i++)fac[i] = 0;
		for(i = 1;i <= m;i++)aa[i] = A[n][i], bb[i] = B[i];
		for(k = 1, phi = mod;k <= prifac[0];phi -= phi / prifac[k++])
			for(i = 1;i <= m;i++){
				for(;!(bb[i] % prifac[k]);bb[i] /= prifac[k], fac[k]++);
				for(;!(aa[i] % prifac[k]);aa[i] /= prifac[k], fac[k]--);
			}
		for(k = j = 1;k <= prifac[0] && fac[k] >= 0;k++)j = (__int128)j * qp(prifac[k], fac[k], mod) % mod;
		if(k > prifac[0]){
			for(i = k = 1;i <= m;i++){
				j = (__int128)j * bb[i] % mod;
				k = (__int128)k * aa[i] % mod;
			}j = (__int128)j * qp(k, phi - 1, mod) % mod;
		}else j = -1;
		printf("%lld\n", j);
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 510ms, 内存消耗: 2040K, 提交时间: 2020-08-10 11:54:56

#include <bits/stdc++.h>
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;
}