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  *a* = 2, *b* = 5  *a* = 2, *b* = 1  *a* = 0, *b* = 1; 70 2. *a* = 31, *b* = 12  *a* = 7, *b* = 12.