codeforces-scrape

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

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 ```