X-Magic Pair
Contest: Educational Codeforces Round 117 (Rated for Div. 2)
Difficulty rating: 1600
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|$$$,

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 format:
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 format:
For the $$$i$$$-th test case, print YES if the corresponding pair $$$(a, b)$$$ is $$$x$$$-magic and NO otherwise.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
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

Example output:
YES
YES
YES
YES
NO
YES
YES
YES

Editorial:
This problem has a GCD-based solution.
Firstly, lets' try to solve it naively. Always suppose that $$$a > b$$$. If this is not true, let's swap $$$a$$$ and $$$b$$$. Firstly, if $$$b > a - b$$$, let's do $$$b := a - b$$$. Okay, now let's subtract $$$b$$$ from $$$a$$$ until $$$b \ge a - b$$$ again and repeat this algorithm till $$$a = 0$$$ or $$$b = 0$$$. If, after some step, we get $$$a = x$$$ or $$$b = x$$$, we are done, and the answer is YES. If $$$a = 0$$$ or $$$b = 0$$$, and we didn't get $$$x$$$ then the answer is NO.
Okay, we can see that we always subtract the minimum possible $$$b$$$ from $$$a$$$ and trying to maintain this condition. It can be proven that this algorithm yields all possible integers that are obtainable by any sequence of the operations from the problem statement (either in $$$a$$$ or in $$$b$$$).
Now we have to speed up this solution somehow. Obviously, most operations are redundant for us in this particular problem. The first thing is that we can skip all operations till $$$b$$$ becomes greater than $$$a - b$$$. The number of such operations is $$$\lfloor\frac{a - b}{2b}\rfloor$$$. And the second thing is that we can skip all operations till we get $$$x$$$ in $$$a$$$. The number of such operations is $$$\lfloor\frac{a-x}{b}\rfloor$$$. For simplicity, this part can be also written as $$$\lfloor\frac{a-x}{2b}\rfloor$$$. This doesn't affect the time complexity much, but the formula for the final number of operations we can skip will be simpler. This number equals $$$cnt = max(1, \lfloor\frac{a-max(b, x)}{2b}\rfloor)$$$ (in fact, we take the minimum between two values written above, because we don't want to skip any of these two cases). So, we can transform the pair $$$(a, b)$$$ to the pair $$$(a - b * cnt, b)$$$ and continue this algorithm.
There are also simpler approaches using the same idea but in a cooler way.
Time complexity: $$$O(\log{a})$$$ per test case.