1933C.md (2544B)
1 Source: https://codeforces.com/problemset/problem/1933/C 2 3 C. Turtle Fingers: Count the Values of k 4 5 time limit per test 6 7 5 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given three positive integers $a$, $b$ and $l$ ($a,b,l \gt 0$). 22 23 It can be shown that there always exists a way to choose non-negative (i.e. $\ge 0$) integers $k$, $x$, and $y$ such that $l = k \cdot a^x \cdot b^y$. 24 25 Your task is to find the number of distinct possible values of $k$ across all such ways. 26 27 Input 28 29 The first line contains the integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 30 31 The following $t$ lines contain three integers, $a$, $b$ and $l$ ($2 \le a, b \le 100$, $1 \le l \le 10^6$) — description of a test case. 32 33 Output 34 35 Output $t$ lines, with the $i$-th ($1 \le i \le t$) line containing an integer, the answer to the $i$-th test case. 36 37 Example 38 39 Input 40 41 ``` 42 11 43 44 2 5 20 45 46 2 5 21 47 48 4 6 48 49 50 2 3 72 51 52 3 5 75 53 54 2 2 1024 55 56 3 7 83349 57 58 100 100 1000000 59 60 7 3 2 61 62 2 6 6 63 64 17 3 632043 65 ``` 66 67 Output 68 69 ``` 70 6 71 1 72 5 73 12 74 6 75 11 76 24 77 4 78 1 79 3 80 24 81 ``` 82 83 Note 84 85 In the first test case, $a=2, b=5, l=20$. The possible values of $k$ (and corresponding $x,y$) are as follows: 86 87 * Choose $k = 1, x = 2, y = 1$. Then $k \cdot a^x \cdot b^y = 1 \cdot 2^2 \cdot 5^1 = 20 = l$. 88 * Choose $k = 2, x = 1, y = 1$. Then $k \cdot a^x \cdot b^y = 2 \cdot 2^1 \cdot 5^1 = 20 = l$. 89 * Choose $k = 4, x = 0, y = 1$. Then $k \cdot a^x \cdot b^y = 4 \cdot 2^0 \cdot 5^1 = 20 = l$. 90 * Choose $k = 5, x = 2, y = 0$. Then $k \cdot a^x \cdot b^y = 5 \cdot 2^2 \cdot 5^0 = 20 = l$. 91 * Choose $k = 10, x = 1, y = 0$. Then $k \cdot a^x \cdot b^y = 10 \cdot 2^1 \cdot 5^0 = 20 = l$. 92 * Choose $k = 20, x = 0, y = 0$. Then $k \cdot a^x \cdot b^y = 20 \cdot 2^0 \cdot 5^0 = 20 = l$. 93 94 In the second test case, $a=2, b=5, l=21$. Note that $l = 21$ is not divisible by either $a = 2$ or $b = 5$. Therefore, we can only set $x = 0, y = 0$, which corresponds to $k = 21$. 95 96 In the third test case, $a=4, b=6, l=48$. The possible values of $k$ (and corresponding $x,y$) are as follows: 97 98 * Choose $k = 2, x = 1, y = 1$. Then $k \cdot a^x \cdot b^y = 2 \cdot 4^1 \cdot 6^1 = 48 = l$. 99 * Choose $k = 3, x = 2, y = 0$. Then $k \cdot a^x \cdot b^y = 3 \cdot 4^2 \cdot 6^0 = 48 = l$. 100 * Choose $k = 8, x = 0, y = 1$. Then $k \cdot a^x \cdot b^y = 8 \cdot 4^0 \cdot 6^1 = 48 = l$. 101 * Choose $k = 12, x = 1, y = 0$. Then $k \cdot a^x \cdot b^y = 12 \cdot 4^1 \cdot 6^0 = 48 = l$. 102 * Choose $k = 48, x = 0, y = 0$. Then $k \cdot a^x \cdot b^y = 48 \cdot 4^0 \cdot 6^0 = 48 = l$.