CF527A.Playing with Paper

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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.

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.

Can you determine how many ships Vasya will make during the lesson?

输入格式

The first line of the input contains two integers $a$ , $b$ ( $1<=b<a<=10^{12}$ ) — the sizes of the original sheet of paper.

输出格式

Print a single integer — the number of ships that Vasya will make.

输入输出样例

输入#1
```
2 1
```
输出#1
```
2
```
输入#2
```
10 7
```
输出#2
```
6
```
输入#3
```
1000000000000 1
```
输出#3
```
1000000000000
```

说明/提示

Pictures to the first and second sample test.

首页