Codeforces Round 929 (Div. 3) |
---|
Закончено |
Вам даны три положительных целых числа $$$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$$$-й набор входных данных.
112 5 202 5 214 6 482 3 723 5 752 2 10243 7 83349100 100 10000007 3 22 6 617 3 632043
6 1 5 12 6 11 24 4 1 3 24
В первом наборе входных данных примера $$$a=2, b=5, l=20$$$. Возможные значения $$$k$$$ (и соответствующие $$$x,y$$$) следующие:
Во втором наборе входных данных примера $$$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$$$) следующие:
Название |
---|