#P17236. [2025年南开中学集训]整除

[2025年南开中学集训]整除

B. 整除(div)

求有多少个正整数 xx 满足

c0xa0+c1xa1+⋯+cn−1xan−1c_0x^{a_0}+c_1x^{a_1}+\cdots+c_{n-1}x^{a_{n-1}}

能被

x0+x1+⋯+xm−1x^0+x^1+\cdots+x^{m-1}

整除,其中 cc 和 aa 是两个给定的序列。

输入格式

第一行一个整数 tt(1≤t≤1051\le t\le 10^5),表示数据组数。

每组数据第一行两个整数 n,mn,m(1≤n≤1051\le n\le 10^5,1≤m≤1091\le m\le 10^9),接下来 nn 行每行两个整数 cic_i 和 aia_i(∣ci∣=1|c_i|=1,0≤ai≤1090\le a_i\le 10^9)。

所有数据中 nn 的总和不超过 10510^5。

输出格式

对于每组数据,如果有无穷个正整数满足条件,则输出 −1-1,否则输出满足条件的正整数个数。

样例

样例输入 1

3
5 2
1 0
1 0
1 0
1 0
1 0
5 3
-1 2
-1 1
-1 0
1 1
-1 1
12 3
-1 0
-1 7
1 8
1 8
-1 4
-1 6
1 8
1 2
1 5
1 2
-1 9
1 5

样例输出 1

1
-1
2

子任务

  • Subtask 1(10 points): t,n,m≤10t,n,m\le 10。
  • Subtask 2(30 points): t≤10t\le 10,n,m≤1000n,m\le 1000。
  • Subtask 3(60 points): 无额外限制。