← 返回题目列表

Codeforces · 1933/C

C. 海龟手指:计算 k 的值

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

给定三个正整数 $$$a$$$、$$$b$$$ 和 $$$l$$$ ($$$a,b,l>0$$$)。

可以证明,总是存在一种选择非负(即 $$$\ge 0$$$)整数 $$$k$$$、$$$x$$$ 和 $$$y$$$ 的方法,使得 $$$l = k \cdot a^x \cdot b^y$$$。

您的任务是在所有这些方式中找到 $$$k$$$ 的不同可能值的数量。

输入

第一行包含整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

以下 $$$t$$$ 行包含三个整数:$$$a$$$、$$$b$$$ 和 $$$l$$$ ($$$2 \le a, b \le 100$$$, $$$1 \le l \le 10^6$$$) - 测试用例的描述。

输出

输出 $$$t$$$ 行,其中第 $$$i$$$ ($$$1 \le i \le t$$$) 行包含一个整数,即第 $$$i$$$ 测试用例的答案。

示例

输入 #1

11
2 5 20
2 5 21
4 6 48
2 3 72
3 5 75
2 2 1024
3 7 83349
100 100 1000000
7 3 2
2 6 6
17 3 632043

输出 #1

6
1
5
12
6
11
24
4
1
3
24

注意

在第一个测试用例中,$$$a=2,b=5,l=20$$$。 $$$k$$$(以及对应的$$$x,y$$$)的可能值如下:

- 选择$$$k = 1,x = 2,y = 1$$$。然后 $$$k \cdot a^x \cdot b^y = 1 \cdot 2^2 \cdot 5^1 = 20 = l$$$。
- 选择$$$k = 2,x = 1,y = 1$$$。然后 $$$k \cdot a^x \cdot b^y = 2 \cdot 2^1 \cdot 5^1 = 20 = l$$$。
- 选择$$$k = 4,x = 0,y = 1$$$。然后 $$$k \cdot a^x \cdot b^y = 4 \cdot 2^0 \cdot 5^1 = 20 = l$$$。
- 选择$$$k = 5,x = 2,y = 0$$$。然后 $$$k \cdot a^x \cdot b^y = 5 \cdot 2^2 \cdot 5^0 = 20 = l$$$。
- 选择$$$k = 10,x = 1,y = 0$$$。然后 $$$k \cdot a^x \cdot b^y = 10 \cdot 2^1 \cdot 5^0 = 20 = l$$$。
- 选择$$$k = 20,x = 0,y = 0$$$。然后 $$$k \cdot a^x \cdot b^y = 20 \cdot 2^0 \cdot 5^0 = 20 = l$$$。

在第二个测试用例中,$$$a=2,b=5,l=21$$$。请注意,$$$l = 21$$$ 不能被 $$$a = 2$$$ 或 $$$b = 5$$$ 整除。因此,我们只能设置$$$x = 0, y = 0$$$,对应$$$k = 21$$$。

在第三个测试用例中,$$$a=4,b=6,l=48$$$。 $$$k$$$(以及对应的$$$x,y$$$)的可能值如下:

- 选择$$$k = 2,x = 1,y = 1$$$。然后 $$$k \cdot a^x \cdot b^y = 2 \cdot 4^1 \cdot 6^1 = 48 = l$$$。
- 选择$$$k = 3,x = 2,y = 0$$$。然后 $$$k \cdot a^x \cdot b^y = 3 \cdot 4^2 \cdot 6^0 = 48 = l$$$。
- 选择$$$k = 8,x = 0,y = 1$$$。然后 $$$k \cdot a^x \cdot b^y = 8 \cdot 4^0 \cdot 6^1 = 48 = l$$$。
- 选择$$$k = 12,x = 1,y = 0$$$。然后 $$$k \cdot a^x \cdot b^y = 12 \cdot 4^1 \cdot 6^0 = 48 = l$$$。
- 选择$$$k = 48,x = 0,y = 0$$$。然后 $$$k \cdot a^x \cdot b^y = 48 \cdot 4^0 \cdot 6^0 = 48 = l$$$。