1612D.md (1379B)
1 Source: https://codeforces.com/problemset/problem/1612/D 2 3 D. X-Magic Pair 4 5 time limit per test 6 7 2 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 You are given a pair of integers $(a, b)$ and an integer $x$. 22 23 You can change the pair in two different ways: 24 25 * set (assign) $a := |a - b|$; 26 * set (assign) $b := |a - b|$, 27 28 where $|a - b|$ is the absolute difference between $a$ and $b$. 29 30 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). 31 32 Your task is to find out if the pair $(a, b)$ is $x$-magic or not. 33 34 You have to answer $t$ independent test cases. 35 36 Input 37 38 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. 39 40 The only line of the test case contains three integers $a$, $b$ and $x$ ($1 \le a, b, x \le 10^{18}$). 41 42 Output 43 44 For the $i$-th test case, print YES if the corresponding pair $(a, b)$ is $x$-magic and NO otherwise. 45 46 Example 47 48 Input 49 50 ``` 51 8 52 6 9 3 53 15 38 7 54 18 8 8 55 30 30 30 56 40 50 90 57 24 28 20 58 365 216 52 59 537037812705867558 338887693834423551 3199921013340 60 ``` 61 62 Output 63 64 ``` 65 YES 66 YES 67 YES 68 YES 69 NO 70 YES 71 YES 72 YES 73 ```