WC2021题解
文章最后更新时间为：2021 年 02 月 12 日 11:28:53
WC2021题解。水平确实不行了，花了好久才把题目补完。
括号路径
符号：$\langle u,v,k\rangle$表示一条$u\to v$的括号编号为$k$的左括号边，$E$为边集。
首先有几个结论：
- 如果$u\to v$存在合法路径，那么$v\to u$也一定存在合法路径。证明比较显然，只要发$u\to v$的路径反着走一遍即可。
- 如果$u\to v$，$v\to x$分别存在合法路径，那么$u\to x$也存在合法路径。把两条路径连起来即可。
- 如果$u\to v$存在合法路径，$x\to u$存在一条左括号边，并且$v\to y$存在一条与之对应的右括号边。那么$x\to y$也存在合法路径。
定义一个等价集合$S$：$\forall u,v\in S$，$u\to v$和$v\to u$都分别存在合法路径。($u\to u$的路径也是合法路径)
那么等价集合也有若干性质：
- 对于任意两个有交的等价集合$S,T$，$S\cup T$也是等价集合。
- 对于任意$u,v(u\ne v)$，存在等价集合$S$，并且$x\in S,\langle u,x,k\rangle, \langle v,x,k\rangle \in E$。那么$\{u,v\}$也是一个等价集合。
- 对于任意$x$，$\{x\}$是一个等价集合。
不难得出：$n$个节点一定可以被划分成若干个极大等价集合，最终答案为$\sum\limits\binom{|S_i|}{2}$。那么问题转化为如何划分等价集合。
定义对于等价集合的函数$\operatorname{Out}_k(S)=\{u|x\in S,\langle u,x,k \rangle\in E\} $。显然$\operatorname{Out}_k(S)$也是一个等价集合。
那么我们考虑这样一个做法：如果存在$x,k$使得$|\operatorname{Out}_k(\{x\})|\ge 2$，我们将$\operatorname{Out}_k(\{x\})$内的所有点看成一个点，并且更新这个点的$\operatorname{Out}$。直到所有点的$\operatorname{Out}$都已经被更新，程序结束。具体实现可以用队列记录需要被更新的点，用$\operatorname{map}$+启发式合并或线段树合并来实现$\operatorname{Out}$的维护，并查集维护等价集合。这里我用线段树合并实现，复杂度$O(m \log m)$，代码如下：
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define mid ((l + r) / 2)
#define rep(i, j, k) for(int i = j; i <= k; ++i)
inline int read() {
int x = 0;
scanf("%d", &x);
return x;
}
typedef long long ll;
using std::vector;
using std::queue;
const int maxn = 3e5 + 5;
const int maxm = 6e5 + 5;
const int LOG = 25;
int n, m, k, root[maxn], cnt, tot, id[maxm * LOG], fa[maxn], siz[maxn], vis[maxm], ROOT;
vector<int> G[maxm];
queue<int> q;
struct node {
int ls, rs;
node(int a = 0, int b = 0) { ls = a; rs = b; }
} t[maxm * LOG];
void insert(int l, int r, int pos, int &p, int x) {
if(!p) p = ++cnt;
if(l == r) {
if(!id[p]) id[p] = ++tot;
G[id[p]].push_back(x);
if(G[id[p]].size() == 2) {
q.push(id[p]);
vis[id[p]] = 1;
} return;
}
if(pos <= mid) insert(l, mid, pos, t[p].ls, x);
else insert(mid + 1, r, pos, t[p].rs, x);
}
int merge(int l, int r, int u, int v) {
if(!u || !v) return u + v;
if(l == r) {
if(G[id[u]].size() < G[id[v]].size()) std::swap(u, v);
for(auto x : G[id[v]]) G[id[u]].push_back(x);
if(G[id[u]].size() > 1 && !vis[id[u]]) {
q.push(id[u]); vis[id[u]] = 1;
}
G[id[v]].clear(); vis[id[v]] = 2;
return u;
}
int lson = merge(l, mid, t[u].ls, t[v].ls);
int rson = merge(mid + 1, r, t[u].rs, t[v].rs);
t[u] = node(lson, rson); t[v] = node(0, 0);
return u;
}
int findx(int x) { return x == fa[x] ? x : fa[x] = findx(fa[x]); }
inline int merge_set(int x, int y) {
x = findx(x); y = findx(y);
if(x == y) return x;
siz[x] += siz[y];
root[x] = merge(1, k, root[x], root[y]);
return fa[y] = x;
}
int main() {
n = read(); m = read(); k = read();
rep(i, 1, n) fa[i] = i, siz[i] = 1;
rep(i, 1, m) {
int x = read(), y = read(), c = read();
insert(1, k, c, root[y], x);
}
while(q.size()) {
int u = q.front(); q.pop();
if(vis[u] == 2) continue;
int x = G[u][0];
for(int i = 1; i < G[u].size(); ++i) x = merge_set(x, G[u][i]);
G[u].clear(); G[u].push_back(x);
vis[u] = 0;
}
ll ans = 0;
rep(i, 1, n) if(findx(i) == i) ans += 1ll * siz[i] * (siz[i] - 1) / 2;
std::cout << ans << std::endl;
return 0;
}表达式求值
先把表示式字符串建成树，树上叶子节点为数字，非叶子节点为>,<,?。先用栈求出和每个右括号匹配的左括号的位置，然后递归建树，假设当前处理的区间为$[l,r]$：
- $E_r$是数字，那么当前节点的
oprator为$E_{r-1}$，左儿子为代表$E_r$的叶子节点，右儿子递归区间$[l,r-2]$。 - $E_r$是右括号(其对应的左括号的位置为$L$)，那么当前节点的
operator为$E_{L-1}$，左儿子递归区间$[L+1,r-1]$，右儿子递归$[l,L-2]$。
建完树后，可以在中序遍历的时候 dp。
70分做法
因为每个位置是独立的，可以分开考虑，对于一个位置考虑令$f_{u,x}$表示处理完$u$这个子树对应的字符串后答案为$x$的方案数。有如下转移：
$$ \begin{cases}f_{u,\min(a,b)}\leftarrow f_{lson_u,a}\times f_{rson_u,b} & \operatorname{opt}_u : \text{< or ?}\\f_{u,\max(a,b)}\leftarrow f_{lson_u,a}\times f_{rson_u,b} & \operatorname{opt}_u : \text{> or ?}\end{cases} $$
把数值离散化后，复杂度为$O(n|E|m^2)$。不含问号直接$O(n|E|)$算，合起来为$70$分。
100分做法
其实我们并不关心每个数具体是多少，只要知道两两的大小关系。还是将每一位分开考虑，假设我们在考虑第$i$个序列的第$j$个，那么这个数被统计的次数等于统计到大于等于它的数的次数减去统计到大于它的数的次数。
- 那么我们将大于等于它的数看成一，小于它的数看成零，做一遍dp，最后答案为一的次数就等于统计到大于等于它的数的次数。
- 同样的我们将大于它的数看成一，小于等于它的数看成零，最后答案为一的次数就等于统计到大于它的数的次数。
而这样的0/1序列只有$2^m$个，我们可以先预处理，然后计算答案的时候直接查表。(上述大小比较均为双关键字比较，先比较数字大小，再比较位置关系，这样可以保证不算重或者先去重)
复杂度$O(2^m|E|+nm^2)$，$100$分代码：
#include <cstdio>
#include <cstring>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
inline int read() {
int x = 0;
scanf("%d", &x);
return x;
}
const int P = 1e9 + 7;
const int maxn = 5e4 + 5;
inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int pls(int x, int y, int z) { return pls(x, pls(y, z)); }
inline int pls(int a, int b, int c, int d) { return pls(a, pls(b, c, d)); }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int mul(int x, int y) { return 1ll * x * y % P; }
int n, m, a[11][maxn], st[maxn], top, ls[maxn * 2], rs[maxn * 2], lb[maxn], rb[maxn], rt, cnt, id[maxn * 2], S, f[maxn * 2][2], g[1105];
char opt[maxn];
void build(int &p, int l, int r) {
if(l > r) return;
if(!p) p = ++cnt;
if(l == r) {
id[p] = r;
return;
}
if(opt[r] == ')') {
id[p] = lb[r] - 1;
build(ls[p], lb[r] + 1, r - 1);
build(rs[p], l, lb[r] - 2);
} else {
id[p] = r - 1;
build(ls[p], r, r);
build(rs[p], l, r - 2);
}
}
void dfs(int p) {
if(!p) return;
if(!ls[p] && !rs[p]) {
int x = S >> (opt[id[p]] - '0') & 1;
f[p][x] = 1; f[p][x ^ 1] = 0; return;
}
dfs(ls[p]); dfs(rs[p]);
if(!ls[p] || !rs[p]) {
f[p][0] = f[ls[p] + rs[p]][0];
f[p][1] = f[ls[p] + rs[p]][1];
return;
}
if(opt[id[p]] == '<') {
f[p][0] = pls(mul(f[ls[p]][0], f[rs[p]][0]), mul(f[ls[p]][0], f[rs[p]][1]), mul(f[ls[p]][1], f[rs[p]][0]));
f[p][1] = mul(f[ls[p]][1], f[rs[p]][1]);
} else if(opt[id[p]] == '>') {
f[p][1] = pls(mul(f[ls[p]][1], f[rs[p]][1]), mul(f[ls[p]][0], f[rs[p]][1]), mul(f[ls[p]][1], f[rs[p]][0]));
f[p][0] = mul(f[ls[p]][0], f[rs[p]][0]);
} else {
f[p][0] = pls(mul(f[ls[p]][0], f[rs[p]][0]), mul(f[ls[p]][0], f[rs[p]][1]), mul(f[ls[p]][1], f[rs[p]][0]), mul(f[ls[p]][0], f[rs[p]][0]));
f[p][1] = pls(mul(f[ls[p]][1], f[rs[p]][1]), mul(f[ls[p]][0], f[rs[p]][1]), mul(f[ls[p]][1], f[rs[p]][0]), mul(f[ls[p]][1], f[rs[p]][1]));
} return;
}
int main() {
n = read(); m = read();
rep(i, 1, m) rep(j, 1, n) a[i][j] = read();
scanf("%s", opt + 1);
int len = strlen(opt + 1);
rep(i, 1, len) {
if(opt[i] == '(') st[++top] = i;
if(opt[i] == ')') {
lb[i] = st[top];
rb[st[top]] = i;
top--;
}
}
build(rt, 1, len);
for(S = 0; S < (1 << m); S++) {
dfs(rt);
g[S] = f[rt][1];
}
int ans = 0;
rep(i, 1, n) {
rep(j, 1, m) {
int T = 0;
rep(k, 1, m) if(a[k][i] > a[j][i] || (a[k][i] == a[j][i] && k >= j)) T |= (1 << k - 1);
ans = pls(ans, mul(dec(g[T], g[T ^ (1 << j - 1)]), a[j][i]));
}
}
printf("%d\n", ans);
return 0;
}斐波那契
首先$F_n=bf_n+af_{n-1}$，$f_n=\begin{cases}0,&n=0\\1,&n=1\\f_{n-2}+f_{n-1},&n\ge 2\end{cases}$。
证明如下：
$$ \begin{aligned} \begin{bmatrix}f_{n-1}\\f_n\end{bmatrix}&=M\begin{bmatrix}f_{n-2}\\f_{n-1}\end{bmatrix}\\ M&=\begin{bmatrix}0&1\\1&1\end{bmatrix}\\ \begin{bmatrix}f_{n-1}\\f_n\end{bmatrix}&=M^{n-1}\begin{bmatrix}f_{0}\\f_{1}\end{bmatrix}\\ \begin{bmatrix}F_{n-1}\\F_n\end{bmatrix}&=M^{n-1}\begin{bmatrix}F_{0}\\F_{1}\end{bmatrix}\\ \end{aligned} $$
不妨令$M^{n-1}=\begin{bmatrix}A&B\\C&D\end{bmatrix}$，$f_{n-1}=B,f_n=D,F_n=aC+bD$，并且不难证明$B=C$，所以$F_n=bf_n+af_{n-1}$。
做法一
考虑$bf_n+af_{n-1}\equiv 0\pmod m\iff \frac{b}{d}f_n+\frac{a}{d}f_{n-1}\equiv 0 \pmod{\frac{m}{d}},d=\gcd(a,b,m)$。
令$a^\prime\leftarrow \frac{a}{d},b^\prime\leftarrow \frac{b}{d},m^\prime\leftarrow\frac{m}{d}，q=\gcd(a',m'),p=\gcd(b',m'), q'=\gcd(f_n,m'), p'=\gcd(f_{n-1},m')$。且因为$\gcd(a^\prime,b^\prime,m^\prime)=1,\gcd(f_n,f_{n-1},m')=1$，所以$\gcd(p,q)=1,\gcd(p',q')=1$。
$$ \begin{aligned} &b'f_n+a'f_{n-1}\equiv 0\pmod{m'}\\ \Rightarrow &\begin{cases}pq\mid b'f_n+a'f_{n-1}\\p'q'\mid b'f_n+a'f_{n-1}\end{cases}\\ \Rightarrow &\begin{cases}p\mid b'f_n+a'f_{n-1}\\q\mid b'f_n+a'f_{n-1}\\p'\mid b'f_n+a'f_{n-1}\\q'\mid b'f_n+a'f_{n-1}\end{cases} \end{aligned} $$
考虑$\begin{cases}q|b'f_n+a'f_{n-1}\\q'|b'f_n+a'f_{n-1}\end{cases}$，且$q\nmid b',q'\nmid f_{n-1}$，所以$\begin{cases}q\mid f_n\\q'\mid a\end{cases}$，故有：
$$ \begin{cases}q\mid f_n\\q'\mid a\end{cases}\Rightarrow \begin{cases}q\mid\gcd(f_n,m')\\q'\mid \gcd(a',m')\end{cases}\Rightarrow \begin{cases}\gcd(a',m')\mid \gcd(f_n,m')\\ \gcd(f_n,m')\mid \gcd(a',m')\end{cases}\Rightarrow \gcd(a',m')=\gcd(f_n,m') $$
同理可证：$\gcd(f_{n-1},m')=\gcd(b',m')$。
$$ \begin{aligned} &b'f_n+a'f_{n-1}\equiv 0\pmod {m'}\\ \Rightarrow & \frac{b'}{p}\frac{f_n}{q}+\frac{a'}{q}\frac{f_{n-1}}{p}\equiv 0\pmod{\frac{m'}{pq}}\\ \Rightarrow &\frac{f_n/q}{f_{n-1}/p}\equiv -\frac{a'/q}{b'/p} \pmod{\frac{m'}{pq}} \end{aligned} $$
然后我们可以直接枚举$m'$然后将所有的$\left(p,q,\frac{f_n/q}{f_{n-1}/p}\mod \frac{m'}{pq}\right)$存下来，询问时直接查表即可。由于$f$在模$m$下的循环节是$O(m)$的，所以复杂度为$O(n\log m+m\log m\log\log m)$。($m$的因数和约为$O(m\log\log m)$)
代码如下：
#include <cstdio>
#include <map>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
inline int read() {
int x = 0;
scanf("%d", &x);
return x;
}
struct node {
int p, q, frac;
node(int a = 0, int b = 0, int c = 0) { p = a; q = b; frac = c; }
bool operator < (const node &t) const {
return p != t.p ? p < t.p : (q != t.q ? q < t.q : frac < t.frac);
}
} ;
const int maxn = 1e5 + 5;
using std::map;
int n, m;
map<node, int> mp[maxn];
int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }
void exgcd(int x, int y, int &a, int &b) {
if(y == 0) { a = 1; b = 0; return; }
exgcd(y, x % y, a, b);
int tmp = b; b = a - x / y * b; a = tmp;
}
int Inv(int a, int m) {
int inv = 0, k = 0; exgcd(a, m, inv, k);
return (inv % m + m) % m;
}
inline void pre_solve() {
rep(i, 2, m) if(m % i == 0) {
int f1 = 0, f2 = 1;
for(int j = 1; ; ++j) {
if(f1 && f2) {
int p = gcd(f1, i), q = gcd(f2, i), z = i / p / q;
int inv = 1ll * Inv(f1 / p, z) * (f2 / q) % z;
if(!mp[i].count(node(p, q, inv))) mp[i][node(p, q, inv)] = j;
}
int tmp = f2; f2 = (f1 + f2) % i; f1 = tmp;
if(f1 == 0 && f2 == 1) break;
}
}
}
inline void main_solve() {
rep(i, 1, n) {
int a = read(), b = read(), d = gcd(m, gcd(a, b));
if(a == 0) { puts("0"); continue; }
if(b == 0) { puts("1"); continue; }
int z = m / d; a /= d; b /= d;
int p = gcd(b, z), q = gcd(a, z); z = z / p / q;
int inv = (z - 1ll * Inv(b / p, z) * (a / q) % z) % z;
if(mp[m / d].count(node(p, q, inv))) printf("%d\n", mp[m / d][node(p, q, inv)]);
else puts("-1");
}
}
int main() {
n = read(); m = read();
pre_solve();
main_solve();
return 0;
}做法二
考虑$m=p^c$该怎么做，如果可以做的话可以用ExCRT求解模循环节意义下的同余方程。
$1^{\circ}$ 若$p^c\mid a,p^c\mid b$。解集为$\mathbb{Z}$。
$2^{\circ}$ 若$p^c \nmid a, p^c \mid b$。令$\gcd(a,b,m)=d=p^x(x<c),a^\prime\leftarrow \frac{a}{d},b^\prime\leftarrow \frac{b}{d},m^\prime\leftarrow\frac{m}{d}$，那么有$f_nb'+f_{n-1}a'\equiv 0\pmod{m'}$，因为$m'\mid b'$，所以$m' \mid f_{n-1}$。
$3^{\circ}$ 若$p^c \mid a, p^c \nmid b$。同理可证：$m'\mid f_n$。
$4^{\circ}$ 若$p^c \nmid a, p^c\nmid b$。
令$\gcd(a,b,m)=d=p^x(x<c),a^\prime\leftarrow \frac{a}{d},b^\prime\leftarrow \frac{b}{d},m^\prime\leftarrow\frac{m}{d}$，那么有$f_nb'+f_{n-1}a'\equiv 0\pmod{m'}$。
- 如果$p\nmid a'$，$\frac{b'}{a'}f_{n}+f_{n-1}\equiv 0\pmod{m'}$，又因为$p\mid \frac{b'}{a'}f_{n}+f_{n-1}$，所以$p\mid f_{n-1}$，且$\gcd(f_{n},f_{n-1})=1$，则$p\nmid f_n$，故有：$\frac{f_{n-1}}{f_n}\equiv -\frac{b'}{a'}\pmod{m'}$。
- 如果$p\nmid b'$，$\frac{a'}{b'}f_{n-1}+f_{n}\equiv 0\pmod{m'}$，又因为$p\mid \frac{a'}{b'}f_{n-1}+f_{n}$，所以$p\mid f_{n}$，且$\gcd(f_{n},f_{n-1})=1$，则$p\nmid f_{n-1}$，故有：$\frac{f_{n}}{f_{n-1}}\equiv -\frac{a'}{b'}\pmod{m'}$。
综上我们只要预处理出$f$中在模$m'$意义下为0的位置。以及$\frac{f_{n}}{f_{n-1}}\mod m'$和$\frac{f_{n-1}}{f_n}\mod m'$的值即可。
最后，如果$m=\prod\limits p_{i}^{c_i}$，我们对于每个$p_i^{c_i}$求出满足条件的位置的集合${S_i}$，那么问题转化为就求解($T$表示循环节长度)：
$$ \begin{cases}x\in S_1\mod T\left(\frac{p_1^{c_1}}{\gcd(a,b,p_1^{c_1})}\right)\\x\in S_2\mod T\left(\frac{p_2^{c_2}}{\gcd(a,b,p_2^{c_2})}\right)\\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\\x\in S_n\mod T\left(\frac{p_2^{c_n}}{\gcd(a,b,p_n^{c_n})}\right)\end{cases} $$
直接暴力枚举所有的余数组合然后ExCRT合并即可。复杂度不太会算，但是可以过，而且跑得很快。
代码如下：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
inline int read() {
int x = 0;
scanf("%d", &x);
return x;
}
const int maxn = 1e5 + 5;
using std::vector;
int n, m, pri[20][2], tot, Len[20], A[10], id[maxn][20], mul_pri[20], prime[10][2], cnt, len[20];
vector<int> f[20][maxn][2], now[10], g[20];
int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }
void exgcd(int x, int y, int &a, int &b) {
if(y == 0) { a = 1; b = 0; return; }
exgcd(y, x % y, a, b);
int tmp = b; b = a - x / y * b; a = tmp;
}
int Inv(int a, int m) {
int inv = 0, k = 0; exgcd(a, m, inv, k);
return (inv % m + m) % m;
}
inline void insert(int i, int c) {
id[i][c] = ++tot;
pri[tot][0] = i; pri[tot][1] = c;
mul_pri[tot] = (c == 1 ? i : mul_pri[id[i][c - 1]] * i);
int f1 = 0, f2 = 1;
g[tot].push_back(0);
for(int j = 1; ; ++j) {
if(f1 % i != 0) {
int inv = 1ll * Inv(f1, mul_pri[tot]) * f2 % mul_pri[tot];
f[tot][inv][0].push_back(j);
}
if(f2 % i != 0) {
int inv = 1ll * Inv(f2, mul_pri[tot]) * f1 % mul_pri[tot];
f[tot][inv][1].push_back(j);
}
if(f2 == 0) g[tot].push_back(j);
int tmp = f2; f2 = (f1 + f2) % mul_pri[tot]; f1 = tmp;
if(f1 == 0 && f2 == 1) { Len[tot] = j; break; }
}
}
inline void pre_solve() {
int x = m;
for(int i = 2; i * i <= x; ++i) {
if(x % i == 0) {
++cnt;
prime[cnt][0] = i;
prime[cnt][1] = 1;
int lim = 0; while(x % i == 0) lim++, x /= i, prime[cnt][1] *= i;
rep(j, 1, lim) insert(i, j);
}
}
if(x != 1) {
++cnt;
prime[cnt][0] = x;
prime[cnt][1] = x;
insert(x, 1);
}
}
int ans = 0;
int dfs(int x, int a = -1, int m = 0) {
if(x == cnt + 1) {
if(a != -1) ans = std::min(ans, a);
return a;
}
if(now[x].size() == 0) dfs(x + 1, a, m);
for(auto v : now[x]) {
if(a == -1 && m == 0) {
int rnt = dfs(x + 1, v, len[x]);
} else {
int d = gcd(m, len[x]);
if((a - v) % d != 0) continue;
int k1 = 0, k2 = 0, m1 = m * len[x] / d;
exgcd(m / d, len[x] / d, k1, k2);
int rnt = dfs(x + 1, ((v + 1ll * k2 * len[x] * ((a - v) / d) % m1) % m1 + m1) % m1, m1);
}
} return -1;
}
inline int solve(int a, int b) {
a %= m; b %= m;
if(a == 0) return 0;
if(b == 0) return 1;
rep(i, 1, cnt) {
now[i].clear();
if((a % prime[i][1] == 0) && (b % prime[i][1] == 0)) continue;
int x = 0, d = gcd(gcd(a, b), prime[i][1]);
while(d % prime[i][0] == 0) x++, d /= prime[i][0];
d = gcd(gcd(a, b), prime[i][1]);
int c = 0, z = prime[i][1]; while(z % prime[i][0] == 0) c++, z /= prime[i][0];
if(a % prime[i][1] == 0) {
now[i] = g[id[prime[i][0]][c - x]];
len[i] = Len[id[prime[i][0]][c - x]];
} else if(b % prime[i][1] == 0) {
now[i] = g[id[prime[i][0]][c - x]];
for(int j = 0; j < now[i].size(); ++j) now[i][j]++;
len[i] = Len[id[prime[i][0]][c - x]];
} else {
int a1 = a / d, b1 = b / d, m1 = prime[i][1] / d;
if(b1 % prime[i][0] != 0) {
int inv = (m1 - 1ll * a1 * Inv(b1, m1) % m1) % m1;
now[i] = f[id[prime[i][0]][c - x]][inv][0];
} else if(a1 % prime[i][0] != 0) {
int inv = (m1 - 1ll * b1 * Inv(a1, m1) % m1) % m1;
now[i] = f[id[prime[i][0]][c - x]][inv][1];
}
len[i] = Len[id[prime[i][0]][c - x]];
}
if(now[i].size() == 0) return -1;
}
ans = 0x3f3f3f3f;
dfs(1);
return (ans == (0x3f3f3f3f) ? -1 : ans);
}
inline void main_solve() {
while(n--) {
int a = read(), b = read();
printf("%d\n", solve(a, b));
}
}
int main() {
n = read(); m = read();
pre_solve();
main_solve();
return 0;
}