A4. 不可逆的重启器 - 2018 团体程序设计天梯赛分组赛暨 3 月内部选拔

仪表盘所有提交榜单

单点时限: 1.0 sec

内存限制: 256 MB

世界线 ${0.337187}^{α}$ ，由于时间机器的损坏，来自 2036 年的时间旅行者铃羽在从 2010 年跳跃至 1975 年时失败了，失忆整整 24 年之后才回想起自己此行的任务，一年后抱憾自杀。

但是，你发现了失败的真正原因，如果 $s$ 和 $t$ 不互质，那么从 $s$ 年跳往 $t$ 年就会失败，但是可以多次跳跃以达到目的（跳跃范围为正整数）。现在你需要告诉 2010 年的铃羽她从 $s$ 年跳跃至 $t$ 年所需要的最少的跳跃次数，来改变世界的支配构造。

输入两个整数 $s, t$ ( $1 \leq s, t \leq 10^{18}, s \neq t$ )。

输出最少跳跃次数。

Input

2018 2017

Output

两个数互质当且仅当它们的最大公约数等于 $1$ 。

NaN

比赛状态发生变化，点 OK 刷新。

OK

2018 团体程序设计天梯赛分组赛暨 3 月内部选拔