codeforces-scrape

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

946B.md (1702B)


      1 Source: https://codeforces.com/problemset/problem/946/B
      2 
      3 B. Weird Subtraction Process
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You have two variables *a* and *b*. Consider the following sequence of actions performed with these variables:
     22 
     23 1. If *a* = 0 or *b* = 0, end the process. Otherwise, go to step 2;
     24 2. If *a* ≥ 2·*b*, then set the value of *a* to *a* - 2·*b*, and repeat step 1. Otherwise, go to step 3;
     25 3. If *b* ≥ 2·*a*, then set the value of *b* to *b* - 2·*a*, and repeat step 1. Otherwise, end the process.
     26 
     27 Initially the values of *a* and *b* are positive integers, and so the process will be finite.
     28 
     29 You have to determine the values of *a* and *b* after the process ends.
     30 
     31 Input
     32 
     33 The only line of the input contains two integers *n* and *m* (1 ≤ *n*, *m* ≤ 1018). *n* is the initial value of variable *a*, and *m* is the initial value of variable *b*.
     34 
     35 Output
     36 
     37 Print two integers — the values of *a* and *b* after the end of the process.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 12 5
     45 ```
     46 
     47 Output
     48 
     49 ```
     50 0 1
     51 ```
     52 
     53 Input
     54 
     55 ```
     56 31 12
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 7 12
     63 ```
     64 
     65 Note
     66 
     67 Explanations to the samples:
     68 
     69 1. *a* = 12, *b* = 5 ![](https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png) *a* = 2, *b* = 5 ![](https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png) *a* = 2, *b* = 1 ![](https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png) *a* = 0, *b* = 1;
     70 2. *a* = 31, *b* = 12 ![](https://espresso.codeforces.com/70a0795f45d32287dba0eb83fc4a3f470c6e5537.png) *a* = 7, *b* = 12.