C. Turtle Fingers: Count the Values of k
brute force; implementation; math; number theory
You are given three positive integers \(a\), \(b\) and \(l\) (\(a,b,l>0\)). 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\). Your task is to find the number of distinct possible values of \(k\) across all such ways.
The first line contains the integer \(t\) (\(1 \le t \le 10^4\)) — the number of test cases.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.
Output \(t\) lines, with the \(i\)-th (\(1 \le i \le t\)) line containing an integer, the answer to the \(i\)-th test case.
In the first test case, \(a=2, b=5, l=20\). The possible values of \(k\) (and corresponding \(x,y\)) are as follows: Choose \(k = 1, x = 2, y = 1\). Then \(k \cdot a^x \cdot b^y = 1 \cdot 2^2 \cdot 5^1 = 20 = l\). Choose \(k = 2, x = 1, y = 1\). Then \(k \cdot a^x \cdot b^y = 2 \cdot 2^1 \cdot 5^1 = 20 = l\). Choose \(k = 4, x = 0, y = 1\). Then \(k \cdot a^x \cdot b^y = 4 \cdot 2^0 \cdot 5^1 = 20 = l\). Choose \(k = 5, x = 2, y = 0\). Then \(k \cdot a^x \cdot b^y = 5 \cdot 2^2 \cdot 5^0 = 20 = l\). Choose \(k = 10, x = 1, y = 0\). Then \(k \cdot a^x \cdot b^y = 10 \cdot 2^1 \cdot 5^0 = 20 = l\). Choose \(k = 20, x = 0, y = 0\). Then \(k \cdot a^x \cdot b^y = 20 \cdot 2^0 \cdot 5^0 = 20 = l\). 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\).In the third test case, \(a=4, b=6, l=48\). The possible values of \(k\) (and corresponding \(x,y\)) are as follows: Choose \(k = 2, x = 1, y = 1\). Then \(k \cdot a^x \cdot b^y = 2 \cdot 4^1 \cdot 6^1 = 48 = l\). Choose \(k = 3, x = 2, y = 0\). Then \(k \cdot a^x \cdot b^y = 3 \cdot 4^2 \cdot 6^0 = 48 = l\). Choose \(k = 8, x = 0, y = 1\). Then \(k \cdot a^x \cdot b^y = 8 \cdot 4^0 \cdot 6^1 = 48 = l\). Choose \(k = 12, x = 1, y = 0\). Then \(k \cdot a^x \cdot b^y = 12 \cdot 4^1 \cdot 6^0 = 48 = l\). Choose \(k = 48, x = 0, y = 0\). Then \(k \cdot a^x \cdot b^y = 48 \cdot 4^0 \cdot 6^0 = 48 = l\).