Turtle Fingers: Count the Values of k (Codeforces 1933C)
Tags: 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.

Input: 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: Output $$$t$$$ lines, with the $$$i$$$-th ($$$1 \le i \le t$$$) line containing an integer, the answer to the $$$i$$$-th test case.

Note: 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$$$. 

Sample Inputs:
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

Sample Outputs:
6
1
5
12
6
11
24
4
1
3
24

Solution (Python):
def solve():
    (a, b, l) = map(int, input().split())
    if a == b:
        x = 0
        temp = l
        while temp % a == 0:
            temp //= a
            x += 1
        print(x + 1)
        return
    (x, y) = (1, 1)
    ans = 0
    temp = 0
    s = set()
    while l % x == 0:
        num = l // x
        ans += 1
        s.add(num)
        while num % b == 0:
            num //= b
            ans += 1
            s.add(num)
        x *= a
    print(len(s))
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        solve()

Solution (Python):
import math
t = int(input())
for _ in range(t):
    l1 = list(map(int, input().split()))
    a = l1[0]
    b = l1[1]
    l = l1[2]
    maxpower1 = 0
    maxpower2 = 0
    while l % a == 0:
        maxpower1 += 1
        l = l // a
    l = l1[2]
    while l % b == 0:
        maxpower2 += 1
        l = l // b
    l = l1[2]
    if math.gcd(a, b) == 1:
        print((maxpower1 + 1) * (maxpower2 + 1))
    elif a == b:
        print(maxpower1 + 1)
    elif l < a and l < b:
        print('1')
    else:
        c = set()
        c.add(l)
        for i in range(maxpower1 + 1):
            if i != 0:
                l = l / a
            c.add(l)
            z = l
            m = 0
            while z % b == 0:
                z = z / b
                m += 1
                c.add(z)
        print(len(c))

Solution (Python):
import sys
from collections import defaultdict

def solve():
    test_cases = int(sys.stdin.readline())
    for _ in range(test_cases):
        (x, y, z) = map(int, sys.stdin.readline().split())
        if x == y:
            count = 1
            while z % x == 0 and z > 0:
                z //= x
                count += 1
            print(count)
            continue
        count = 0
        indices = [0]
        divisor = 1
        unique_remainders = set()
        original_z = z
        i = 1
        while z % x == 0 and z > 0:
            indices.append(i)
            z //= x
            i += 1
        for index in indices:
            remaining = original_z // divisor
            unique_remainders.add(remaining)
            count += 1
            while remaining % y == 0 and remaining > 0:
                remaining //= y
                unique_remainders.add(remaining)
                count += 1
            divisor *= x
        print(len(unique_remainders))
if __name__ == '__main__':
    solve()