codeforces-scrape

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

1542B.md (1682B)


      1 Source: https://codeforces.com/problemset/problem/1542/B
      2 
      3 B. Plus and Multiply
      4 
      5 time limit per test
      6 
      7 3 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 There is an infinite set generated as follows:
     22 
     23 * $1$ is in this set.
     24 * If $x$ is in this set, $x \cdot a$ and $x+b$ both are in this set.
     25 
     26 For example, when $a=3$ and $b=6$, the five smallest elements of the set are:
     27 
     28 * $1$,
     29 * $3$ ($1$ is in this set, so $1\cdot a=3$ is in this set),
     30 * $7$ ($1$ is in this set, so $1+b=7$ is in this set),
     31 * $9$ ($3$ is in this set, so $3\cdot a=9$ is in this set),
     32 * $13$ ($7$ is in this set, so $7+b=13$ is in this set).
     33 
     34 Given positive integers $a$, $b$, $n$, determine if $n$ is in this set.
     35 
     36 Input
     37 
     38 The input consists of multiple test cases. The first line contains an integer $t$ ($1\leq t\leq 10^5$) — the number of test cases. The description of the test cases follows.
     39 
     40 The only line describing each test case contains three integers $n$, $a$, $b$ ($1\leq n,a,b\leq 10^9$) separated by a single space.
     41 
     42 Output
     43 
     44 For each test case, print "Yes" if $n$ is in this set, and "No" otherwise. You can print each letter in any case.
     45 
     46 Example
     47 
     48 Input
     49 
     50 ```
     51 5
     52 24 3 5
     53 10 3 6
     54 2345 1 4
     55 19260817 394 485
     56 19260817 233 264
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 Yes
     63 No
     64 Yes
     65 No
     66 Yes
     67 ```
     68 
     69 Note
     70 
     71 In the first test case, $24$ is generated as follows:
     72 
     73 * $1$ is in this set, so $3$ and $6$ are in this set;
     74 * $3$ is in this set, so $9$ and $8$ are in this set;
     75 * $8$ is in this set, so $24$ and $13$ are in this set.
     76 
     77 Thus we can see $24$ is in this set.
     78 
     79 The five smallest elements of the set in the second test case is described in statements. We can see that $10$ isn't among them.