codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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