题解区怎么是神秘题解？

下面是一篇正常的题解。

Part 1.

你发现你要算 $B / A \bmod M$，先求出 $G = \gcd (A, M)$。

如果 $B$ 不是 $G$ 的倍数那么答案就是 $\texttt{-1}$，因为约分后 $A$ 中仍剩有 $M$ 的因子，也就是 $A$ 与 $M$ 不互质（没有逆元）。否则你就把 $A, B$ 都除掉 $G$，然后就可以正常算了。

现在难点在于求出 $G$，以及如何把 $A, B$ 给除掉 $G$。

Part 2.

有一个想法是把 $a _ i, M$ 分解质因数，然后对于每个质因子，将其在 $A, M$ 中出现次数取 $\min$，就是其在 $G$ 中的出现次数。

除法的话可以把 $b _ i$ 也分解质因数，对于每个质因子，将其与 $G$ 的抵消掉。

最后如果 $G$ 没有消完，那么就输出 $\texttt {-1}$；否则求出 $A =$ 每个 $a _ i$ 剩下的质因子之积 $\bmod \, M$，和 $B =$ 每个 $b _ i$ 剩下的质因子之积 $\bmod \, M$，答案即为 $B / A \bmod M$，直接 exgcd 求逆元即可。

现在的问题是邪恶的出题人并不想让你分解质因数，那咋办？

Part 3.

我们引入一个概念：我们也许并不需要分解彻底，只需要分解出“伪质因数”就行。

什么意思呢？举个例子：

对于 $30, 35, 42$ 来说：

$30 = 2 \times 3 \times 5 = 6 \times 5$

$35 = 5 \times 7$

$42 = 2 \times 3 \times 7 = 6 \times 7$

发现我们其实只需要分解到 $5, 6, 7$ 即可，可以只分解到 $6$ 是因为质因子 $2$ 和 $3$ 要么同时不出现，要么同时出现，我们可以把它们看做一个整体，即“伪质因数”。

对一些数 $A _ 1, A _ 2, \ldots, A _ m$ 分解“伪质因数”$p _ 1, p _ 2, \ldots, p _ k$ 需要满足两个性质：

1. 两个不同的“伪质因数”互质。
2. 每个 $A _ i$ 都能被表示成 $p _ 1 ^ {c _ 1} p _ 2 ^ {c _ 2} \cdots p _ k ^ {c _ k}$。

现在问题来了，怎么构造“伪质因数”呢？

考虑增量构造，假设之前的“伪质因数”集合为 $S = \{p _ 1, p _ 2, \ldots, p _ k\}$，现在加入一个数 $x$：

• 若存在一个数 $p _ u$ 满足 $p _ u$ 与 $x$ 不互质，设 $w = \gcd (p _ u, x)$，则从 $S$ 中删除 $p _u$，并递归加入 $w$、$p _ u / w$、$x / w$。

• 否则，向 $S$ 中直接加入 $x$。

不懂的地方可以看代码，应该写得挺清楚的。

于是我们可以对所有 $b _ i$ 和 $M$ 分解“伪质因数”，注意我们只关心 $M$ 的因数，所以对于一个 $a _ i$ 实际上加入的是 $\gcd (a _ i, M)$，对于 $b _ i$ 同理，这样“伪质因数”的个数只有 $\log M$ 级别。

接下来就可以把“伪质因数”看成普通的质因数，如 Part 2. 所讲来做就行啦。

Part 4.

接下来讲一讲构造复杂度的证明。

对于一次加入操作，查找 $p _ u$ 是 $|S|$ 级别的。

如果找到符合条件的 $p _ u$，就可能发生分裂 $w, p _ u / w$ 并继续加入 $x / w$：

• 如果发生了分裂操作即 $w < p _ u$，那么 $|S|$ 会增大 $1$，由于最终 $S$ 的大小只有 $|S _ n|$，所以这部分只会带来 $2 |S _ n|$ 次加入操作。

• 接下来会继续递归 $x / w$，由于 $w \ge 2$，所以每次递归 $x$ 至少减半，故对于一次原始的加入操作，至多递归加入 $\text O (\log x)$ 次。

所以单次加入复杂度是 $\text O (|S| \log x)$，均摊部分时间复杂度是 $\text O (|S _ n| ^ 2 \log x)$。

运用到这题，我们有 $m$ 次加入操作，并且加入的都是 $M$ 的因数所以 $|S _ n| = \text O (\log \log M)$，故每次询问复杂度应该是 $\text O ((m + \log \log M) \log M \log \log M)$ 的。

Part 5.

放一下代码。

#include<cstdio>
#include<vector>
#include<set>
#define N 25
#define M 10005
using namespace std;

using ll=long long;
using lll=__int128;
int n,m,q;
ll a[N][M],b[M];
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll exgcd(ll a,ll b,ll &x,ll &y) {
	if(!b) return x=1,y=0,a;
	ll g=exgcd(b,a%b,y,x); y-=a/b*x;
	return g;
}
ll inv(ll x,ll p) {
	// ax=1(mod p) => ax+bp=1
	ll a,b; exgcd(x,p,a,b);
	return (a%p+p)%p;
}
set<ll> s;
void ins(ll x) {
	if(x==1) return;
	for(auto u:s) {
		ll w=gcd(x,u);
		if(w>1) {
			if(w<u) {
				s.erase(u),ins(w),ins(u/w);
			}
			return ins(x/w);
		}
	}
	s.insert(x);
}
int main() {
	scanf("%d%d%d",&n,&m,&q);
	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]);
	for(int _=1,i;_<=q;_++) {
		ll mod; scanf("%d%lld",&i,&mod);
		s.clear(),s.insert(mod);
		for(int j=1;j<=m;j++) ins(gcd(a[i][j],mod)),ins(gcd(b[j],mod));
		vector<ll> p;
		for(auto u:s) p.push_back(u);
		int k=p.size(); ll up=1,dn=1;
		vector<int> c(k);
		for(int j=1;j<=m;j++) {
			ll x=a[i][j];
			for(int u=0;u<k;u++) {
				while(x%p[u]==0) c[u]++,x/=p[u];
			}
			dn=(lll)dn*x%mod;
		}
		for(int j=1;j<=m;j++) {
			ll x=b[j];
			for(int u=0;u<k;u++) {
				while(c[u]>0&&x%p[u]==0) c[u]--,x/=p[u];
			}
			up=(lll)up*x%mod;
		}
		bool fl=1;
		for(int j=0;j<k;j++) if(c[j]>0) {fl=0; break;}
		if(!fl) {
			puts("-1"); continue;
		}
		ll res=(lll)up*inv(dn,mod)%mod;
		printf("%lld\n",res);
	}
	return 0;
}