知道这个结论以后我们每次找到最大的一个 $c\le b$ 满足 $\gcd(c,a)\gt 1$。枚举 $\gcd$，由于 $a$ 最多被除以 $\log a$ 次，所以复杂度是 $\log a\sqrt a$ 的。能过。
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a, b;
int f(int x, int y) {
if (y == 0) return 0;
if (x == y) return 1;
int z = 0;
for (int i = 1; i * i <= x; i++) {
if (x % i == 0) {
i > 1 ? z = max(z, y / i * i) : 0;
x / i > 1 ? z = max(z, y / (x / i) * (x / i)) : 0;
}
}
return y - z + f(x / __gcd(x, z), z / __gcd(x, z));
}
signed main() {
cin >> a >> b;
cout << f(a, b);
return 0;
}
```