X-Magic Pair (Codeforces 1612D)
Tags: Math, number theory

You are given a pair of integers $$$(a, b)$$$ and an integer $$$x$$$.You can change the pair in two different ways:   set (assign) $$$a := |a - b|$$$;  set (assign) $$$b := |a - b|$$$,  where $$$|a - b|$$$ is the absolute difference between $$$a$$$ and $$$b$$$.The pair $$$(a, b)$$$ is called $$$x$$$-magic if $$$x$$$ is obtainable either as $$$a$$$ or as $$$b$$$ using only the given operations (i.e. the pair $$$(a, b)$$$ is $$$x$$$-magic if $$$a = x$$$ or $$$b = x$$$ after some number of operations applied). You can apply the operations any number of times (even zero).Your task is to find out if the pair $$$(a, b)$$$ is $$$x$$$-magic or not.You have to answer $$$t$$$ independent test cases.

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The next $$$t$$$ lines describe test cases.The only line of the test case contains three integers $$$a$$$, $$$b$$$ and $$$x$$$ ($$$1 \le a, b, x \le 10^{18}$$$).

Output: For the $$$i$$$-th test case, print YES if the corresponding pair $$$(a, b)$$$ is $$$x$$$-magic and NO otherwise.


Sample Inputs:
8
6 9 3
15 38 7
18 8 8
30 30 30
40 50 90
24 28 20
365 216 52
537037812705867558 338887693834423551 3199921013340

Sample Outputs:
YES
YES
YES
YES
NO
YES
YES
YES

Solution (Python):
import sys
input = sys.stdin.buffer.readline

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

def ri():
    return int(input())

def rs():
    return input().decode('utf-8')[:-2]

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

def main():
    (a, b, x) = rm()
    while a and b:
        if x == a or x == b:
            return 'YES'
        (a, b) = (min(a, b), max(a, b))
        if x > b:
            return 'NO'
        if x < a:
            (q, r) = divmod(b, a)
            (a, b) = (r, a)
        elif (b - x) % a == 0:
            return 'YES'
        else:
            return 'NO'
    return 'NO'
t = ri()
for i in range(t):
    print(main())

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    (a, b, x) = map(int, input().split())
    (a, b) = (max(a, b), min(a, b))
    if x > a:
        return 'NO'
    while b > 0 and a >= x:
        if (a - x) % b == 0:
            return 'YES'
        (a, b) = (b, a % b)
    return 'NO' if a != x else 'YES'
for _ in range(int(input())):
    print(solve())

Solution (Python):
def my_swap(a, b):
    return (b, a)

def solve(x, y, z):
    if x < y:
        (x, y) = my_swap(x, y)
    if x == z or y == z:
        return True
    if x < z:
        return False
    if y == 0:
        return False
    if (x - z) % y == 0:
        return True
    return solve(y, x % y, z)

def main():
    cas = int(input())
    for _ in range(cas):
        (x, y, z) = map(int, input().split())
        if solve(x, y, z):
            print('YES')
        else:
            print('NO')
if __name__ == '__main__':
    main()