← 返回题目列表

Codeforces · 1912/D

D. 整除性测试

中文机器翻译题面 查看原题

Daisy 最近学习了整数的整除规则,她对它们很着迷。她学到的测试之一是被 3 整除的测试。您可以求一个十进制数所有数字的和,并检查所得的和是否能被 3 整除。此外,所得的数字和与原始数字模 3 一致 - 模 3 的余数被保留。例如,$$$75 \equiv 7 + 5 \pmod 3$$$。黛西对这样的事情特别感兴趣 保留余数 可分性测试。

对于十进制整数(以 10 为基数的整数),她还学到了更多类似的例子:

  • 要测试模 11 的整除性,请找到数字的交替和。从最后一位(最低有效位)开始计数,在奇数位置(最后一位、倒数第三位等)加上奇数位置上的数字,并减去偶数位置(倒数第二位、倒数第四位等)上的数字,以获得与原始数字同余模 11 的和。例如,$$$123 \equiv 1 - 2 + 3 \pmod {11}$$$。
  • 要测试模 4 的整除性,请保留最后一个 两位数。它们的值与原始数模 4 一致。例如,$$$876543 \equiv 43 \pmod 4$$$。
  • 要测试模 7 的整除性,请找到以下组的交替和: 三位数。例如,$$$4389328 \equiv 4 - 389 + 328 \pmod 7$$$。

类似的测试可以在其他基地找到。例如,要测试八进制数(以 8 为底)模 5 的整除性,请找到以下组的交替和: 两位数。例如,$$$1234_8 \equiv -12_8 + 34_8 \pmod 5$$$。

Daisy 想要为给定的基 $$$b$$$ 找到这样的规则。她对三种整除规则感兴趣:

  • 种类 1 — 取以 $$$b$$$ 为基数的整数的最后 $$$k$$$ 位。
  • 种类 2 — 取以 $$$b$$$ 为基数的整数的 $$$k$$$ 位数字的总和。
  • 种类 3 — 取以 $$$b$$$ 为基数的整数的 $$$k$$$ 位的交替和。

并不总是能够找到这样的整除规则。例如,在以 10 为基数的情况下,不存在对模 6 整除的此类测试,尽管存在测试可被 6 整除的不同方法。

给定基 $$$b$$$ 和模 $$$n$$$,Daisy 想知道存在这样的整除性测试的最小组大小 $$$k$$$。

输入

输入中有多项测试。输入的第一行包含一个整数 $$$t$$$ — 测试数量。接下来的 $$$t$$$ 行描述了测试。

每个测试都包含一行,其中包含两个整数 $$$b$$$ 和 $$$n$$$ — 基数和模数 ($$$b, n \ge 2$$$)。输入中所有 $$$b$$$ 值的总和不超过 $$$10^6$$$,并且输入中所有 $$$n$$$ 值的总和不超过 $$$10^6$$$。

输出

写入 $$$t$$$ 行 - 输入中的每个测试一行。如果给定 $$$b$$$ 和 $$$n$$$ 的整除性测试不存在,则在测试行中写入单个整数 $$$0$$$。否则,写两个整数 $$$a$$$ 和 $$$k$$$,其中 $$$a$$$ 是整除性测试的类型(1、2 或 3),$$$k$$$ 是测试组中的位数,这样 $$$k$$$ 是给定 $$$b$$$ 和 $$$n$$$ 的所有可能整除性测试中最低的。

示例

输入
复制

6
10 3
10 11
10 4
10 7
8 5
10 6

输出
复制

2 1
3 1
1 2
3 3
3 2
0