2023 年上海市大学生程序设计竞赛 - 四月赛

A. 宝石划分

单点时限: 1.0 sec

内存限制: 512 MB

茫茫的大海上,有一群海盗,虽然大家都十分贪婪、残暴,但是还算守规则。一次出海,海盗们获得了$N$颗相同的宝石(宝石无法切割)。船上共$M$个海盗,他们希望能够完美地瓜分这些宝石,即每个人获得的宝石数量相同,但是目前可能无法完美地瓜分。于是他们商量了一个办法:如果在座的各位无法完美地瓜分这些宝石,就随机把一个人扔下船,直到可以让每个海盗分到的宝石一样多为止(即$N$需要被最终剩余的人数整除)。

已知宝石数量$N$和初始海盗人数$M$,求最终每个海盗获得的宝石数量。可以证明,到最后一定可以剩下至少一个海盗在船上,并且每个人分到的宝石一样多。

输入格式

一行两个正整数$N$、$M$,中间空格隔开,分别表示宝石数量和初始海盗人数。

输出格式

一个整数表示答案,代表最终每个海盗获得的宝石数量。

样例

Input
3 8
Output
1
Input
8 3
Output
4
Input
8 1
Output
8

提示

$1 \leq N,M\le 10^{12}$