527A.md (1592B)
1 Source: https://codeforces.com/problemset/problem/527/A 2 3 A. Playing with Paper 4 5 time limit per test 6 7 2 seconds 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 One day Vasya was sitting on a not so interesting Maths lesson and making an origami from a rectangular *a* mm × *b* mm sheet of paper (*a* > *b*). Usually the first step in making an origami is making a square piece of paper from the rectangular sheet by folding the sheet along the bisector of the right angle, and cutting the excess part. 22 23  24 25 After making a paper ship from the square piece, Vasya looked on the remaining (*a* - *b*) mm × *b* mm strip of paper. He got the idea to use this strip of paper in the same way to make an origami, and then use the remainder (if it exists) and so on. At the moment when he is left with a square piece of paper, he will make the last ship from it and stop. 26 27 Can you determine how many ships Vasya will make during the lesson? 28 29 Input 30 31 The first line of the input contains two integers *a*, *b* (1 ≤ *b* < *a* ≤ 1012) — the sizes of the original sheet of paper. 32 33 Output 34 35 Print a single integer — the number of ships that Vasya will make. 36 37 Examples 38 39 Input 40 41 ``` 42 2 1 43 ``` 44 45 Output 46 47 ``` 48 2 49 ``` 50 51 Input 52 53 ``` 54 10 7 55 ``` 56 57 Output 58 59 ``` 60 6 61 ``` 62 63 Input 64 65 ``` 66 1000000000000 1 67 ``` 68 69 Output 70 71 ``` 72 1000000000000 73 ``` 74 75 Note 76 77 Pictures to the first and second sample test. 78 79 