Description：

给 $m$ 个数 $b_i$ 和 $n\times m$ 个数 $a_{i,j}$ ，多次询问，每次给出 $x,mod$ ，求： $$ \frac{\prod\limits_{i=1}^mb[i]}{\prod\limits_{i=1}^ma[x][i]}\mod mod $$ $1<mod,a_{i,j},b_i<2\times10^81\leqslant n\leqslant 20,1\leqslant m\leqslant 10^4$

Solution：

关键在于判断无解以及求逆元。

众所周知当分母与模数不互质的时候没有逆元，那么就可以用 $pollard-rho$ 分解 $mod$ ，然后统计次数判断，求逆元的话由于逆元函数是积性函数所以可以分质因子求。

逆元要用扩欧求。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,k;

#define MAXN 22

#define MAXM 10010

typedef long long ll;

ll b[MAXM];

ll a[MAXN][MAXM];

ll fac[MAXN];

ll prime[12] = {2ll,3ll,5ll,7ll,11ll,13ll,17ll,19ll,23ll,29ll,31ll,37ll};

ll mul(ll a,ll b,ll p)

{

	a %= p;b %= p;

	ll res = ((a * b - (ll)(((long double)a * b + 0.5) / p) * p) % p + p) % p;

	return res;

}

ll power(ll a,ll b,ll p)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = mul(res,a,p);

		b = b >> 1;

		a = mul(a,a,p);

	}

	return res;

}

bool check(ll a,ll b,ll p)

{

	if(b & 1)return true;

	ll t = power(a,b >> 1,p);

	if(t == 1)return check(a,b >> 1,p);

	else if(t == p - 1)return true;

	else return false;

}

bool test(ll n)

{

	if(n == 1)return false;

	if(n == 2)return true;

	if((n & 1) == 0)return false;

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

	{

		if(n == prime[i])return true;

		else if(power(prime[i],n - 1,n) != 1)return false;

		else if(!check(prime[i],n - 1,n))return false;

	}

	return true;

}

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

ll rho(ll n,ll c)

{

	ll x = rand() % n,y = x,t = 1;

	for(int i = 1,k = 2;t == 1;++i)

	{

		x = (mul(x,x,n) + c) % n;

		t = gcd(abs(x - y),n);

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

	}

	return t;

}

void solve(ll n)

{

	if(n == 1)return;

	if(test(n)){fac[++fac[0]] = n;return;}

	ll t = n;

	while(t == n)

	{

		t = rho(n,rand() % 5 + 1);

	}

	solve(t);

	solve(n / t);

	return;

}

ll cnt[MAXN];

void getfac(ll k)

{

	fac[0] = 0;

	solve(k);

	sort(fac + 1,fac + 1 + fac[0]);

	fac[0] = unique(fac + 1,fac + 1 + fac[0]) - fac - 1;

	for(int i = 1;i <= fac[0];++i)cnt[i] = 0;

	return;

}

void exgcd(ll a,ll b,ll &x,ll &y)

{

	if(b == 0)

	{

		x = 1;y = 0;

		return;

	}

	exgcd(b,a % b,x,y);

	ll t = x;x = y;

	y = t - a / b * y;

	return;

}

ll inv(ll a,ll m)

{

	ll x,y;

	exgcd(a,m,x,y);

	return (x % m + m) % m;

}

int main()

{

	scanf("%d%d%d",&n,&m,&k);

	for(int i = 1;i <= m;++i)scanf("%lld",&b[i]);

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

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

			scanf("%lld",&a[i][j]);

	int x;

	ll mod;

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

	{

		scanf("%d%lld",&x,&mod);

		getfac(mod);

		ll ans = 1;

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

		{

			ll v = b[p];

			for(int s = 1;s <= fac[0];++s)

				while(v % fac[s] == 0)++cnt[s],v /= fac[s];

			ans = mul(ans,v,mod);

		}

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

		{

			ll v = a[x][p];

			for(int s = 1;s <= fac[0];++s)

				while(v % fac[s] == 0)--cnt[s],v /= fac[s];

			ans = mul(ans,inv(v,mod),mod);

		}

		bool tag = true;

		for(int p = 1;p <= fac[0];++p)

		{

			if(cnt[p] < 0)

			{

				tag = false;

				break;

			}

		}

		if(!tag)

		{

			puts("-1");

			continue;

		}

		for(int p = 1;p <= fac[0];++p)

		{

			ans = mul(ans,power(fac[p],cnt[p],mod),mod);

		}

		cout << ans << endl;

	}

	return 0;

}