← 返回题目列表

Codeforces · 180/B

B. 整除规则

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

Vasya 在学校学习整除规则。以下是其中一些:

- 能被 2 整除。当且仅当一个数字的最后一位数字能被 2 整除,或者换句话说,是偶数时,该数字才能被 2 整除。
- 能被 3 整除。当且仅当一个数字的各位数字之和能被 3 整除时,该数字才能被 3 整除。
- 能被 4 整除。当且仅当一个数字的最后两位数字形成能被 4 整除的数字时,该数字才能被 4 整除。
- 能被 5 整除。当且仅当一个数字的最后一位数字等于 5 或 0 时,该数字才能被 5 整除。
- 能被 6 整除。一个数字能被 6 整除当且仅当它同时能被 2 和 3 整除(即最后一位数字是偶数且所有数字之和能被 3 整除)。
- 能被 7 整除。Vasya 不知道这样的整除规则。
- 能被 8 整除。当且仅当一个数字的最后三位形成能被 8 整除的数字时,该数字才能被 8 整除。
- 能被 9 整除。一个数字能被 9 整除当且仅当其数字之和能被 9 整除。
- 能被 10 整除。当且仅当一个数字的最后一位数字为零时,该数字才能被 10 整除。
- 能被 11 整除。当且仅当一个数字的奇数位置上的数字之和等于偶数位置上的数字之和,或者它们的数字不同且能被 11 整除时,该数字才能被 11 整除。

Vasya 对某些整除规则彼此相似这一事实很感兴趣。事实上,要检查一个数字能否被 2、4、5、8 和 10 整除,检查最后一位或几位数字是否满足某些条件就足够了。 Vasya 将此类规则称为 2 类规则。

如果检查整除性意味着找到数字之和并检查该和是否能被给定数字整除,那么 Vasya 将此规则称为 3 类型规则(因为它适用于数字 3 和 9)。

如果我们需要求奇数位和偶数位上的数字和之间的差,并检查差是否能被给定的除数整除,这个规则称为11型规则(适用于数字11)。

在某些情况下,我们应该将除数分成几个因子,并检查不同类型(2 类、3 类或 11 类)的规则是否适用。例如,对于数字 6,我们检查 2 类型和 3 类型规则,对于数字 66,我们检查所有三种类型。这种混合整除规则称为 6 类规则。

最后,有一些没有规则适用的数字:既不是 2 类型,也不是 3 类型,也不是 11 类型,也不是 6 类型。最小的数字是数字 7,所以我们会说在这种情况下神秘的 7 类型规则起作用,这是 Vasya 尚未发现的规则。

Vasya 的梦想是找到所有可能数字的整除规则。他不会只停留在十进制数字上。由于数量较多,ha一个人不可能全部完成。 Vasya 要求您编写一个程序,确定给定除数 d 的基于 b 的表示法中的整除规则类型。

输入

第一个输入行包含两个整数 b 和 d (2 ≤ b, d ≤ 100) — 表示法系统基数和除数。两个数字均以十进制表示。

输出

在第一个输出行上打印基于 b 的表示法系统中的规则类型,其中除数为 d:“2-type”、“3-type”、“11-type”、“6-type”或“7-type”。如果有多种此类类型,请打印给定序列中较早出现的类型。如果一个数字属于 2 类型,则在第二行打印最后一个基于 b 的数字的最少数量,我们将需要使用它来检查整除性。

示例

输入 #1

10 10

输出 #1

2-type
1

输入 #2

2 3

输出 #2

11-type

注意

二进制表示法中数字 3 的整除规则如下:“当且仅当一个数能被 3 整除时,该数占据偶数位的数字之和不同于占据奇数位的数字之和”。这是 11 种规则。例如,2110 = 101012。对于它,奇数位置上的数字之和等于 1 + 1 + 1 = 3,偶数位置上的数字之和等于 0 + 0 = 0。该规则有效,并且该数字可以被 3 整除。

在某些表示法中,数字可以符合 3 类型规则和 11 类型规则。在这种情况下,正确答案是“3 型”。