Plus and Multiply (Codeforces 1542B)
Tags: Math, number theory

There is an infinite set generated as follows:  $$$1$$$ is in this set.  If $$$x$$$ is in this set, $$$x \cdot a$$$ and $$$x+b$$$ both are in this set. For example, when $$$a=3$$$ and $$$b=6$$$, the five smallest elements of the set are:  $$$1$$$,  $$$3$$$ ($$$1$$$ is in this set, so $$$1\cdot a=3$$$ is in this set),  $$$7$$$ ($$$1$$$ is in this set, so $$$1+b=7$$$ is in this set),  $$$9$$$ ($$$3$$$ is in this set, so $$$3\cdot a=9$$$ is in this set),  $$$13$$$ ($$$7$$$ is in this set, so $$$7+b=13$$$ is in this set). Given positive integers $$$a$$$, $$$b$$$, $$$n$$$, determine if $$$n$$$ is in this set.

Input: 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.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.

Output: For each test case, print "Yes" if $$$n$$$ is in this set, and "No" otherwise. You can print each letter in any case.

Note: In the first test case, $$$24$$$ is generated as follows:  $$$1$$$ is in this set, so $$$3$$$ and $$$6$$$ are in this set;  $$$3$$$ is in this set, so $$$9$$$ and $$$8$$$ are in this set;  $$$8$$$ is in this set, so $$$24$$$ and $$$13$$$ are in this set. Thus we can see $$$24$$$ is in this set.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.

Sample Inputs:
5
24 3 5
10 3 6
2345 1 4
19260817 394 485
19260817 233 264

Sample Outputs:
Yes
No
Yes
No
Yes

Solution (Python):
import sys
import os
from bisect import bisect_left, bisect_right
from math import ceil, floor, gcd, factorial, sqrt, log2, log
import random
from collections import Counter, defaultdict, deque
from functools import cmp_to_key, lru_cache, reduce
from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
from itertools import accumulate, combinations, permutations
from operator import add, iand, ior, itemgetter, mul, xor
from string import ascii_lowercase, ascii_uppercase
from typing import *
input = lambda : sys.stdin.readline().rstrip('\r\n')
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
(dx, dy) = ([0, 1, 0, -1, 1, -1, 1, -1], [1, 0, -1, 0, -1, -1, 1, 1])
inf = float('inf')
mod = int(1000000000.0 + 7)

def solve():
    (n, a, b) = MII()
    if a == 1:
        print('Yes' if (n - 1) % b == 0 else 'No')
        return
    x = 1
    while x <= n:
        if (n - x) % b == 0:
            print('Yes')
            return
        x *= a
    print('No')
    return
if __name__ == '__main__':
    t = 1
    if t:
        t = II()
        for _ in range(t):
            solve()
    else:
        solve()

Solution (Python):
A = ['YES\n', 'NO\n']
s = ''
for _ in range(int(input())):
    i = t = 1
    (n, a, b) = map(int, input().split())
    if a == 1:
        s += A[(n - 1) % b > 0]
        continue
    while i <= n:
        if (n - i) % b == 0:
            t = 0
            break
        i *= a
    s += A[t]
print(s)

Solution (Python):
import sys
in_f = sys.stdin.read(-1).replace('\r\n', '\r')
in_f = in_f.split()
t = int(in_f[0])
index = 0
for tc in range(t):
    (n, a, b) = (int(in_f[index + 1]), int(in_f[index + 2]), int(in_f[index + 3]))
    if a == 1:
        if (n - 1) % b == 0:
            print('YES')
        else:
            print('NO')
    else:
        found = False
        num = 1
        while num <= n:
            if num % b == n % b:
                found = True
                break
            num = num * a
        if found:
            print('YES')
        else:
            print('NO')
    index += 3