欧拉函数

欧拉函数

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

描述

欧拉函数 \(\phi(n)\) 统计了 \(1\) 到 \(n\) 中与 \(n\) 互素的数字个数,例如 \(\phi(9)=6\)。

现在给定正整数 \(A\) 和 \(B\),请找出最小的正整数 \(n\) 满足 \(\frac{\phi(n)}{n-1} < \frac{A}{B}\)。

格式

输入格式

输入只有一行,是两个正整数 \(A\) 和 \(B\),满足 \(1\le A<B\le 10^6\)。

输出格式

输出一个正整数,表示最小满足条件的 \(n\)。

样例1

样例输入1

1 2

样例输出1

6

样例2

样例输入2

2 5

样例输出2

12

限制

对于 \(20\%\) 的数据,保证答案不超过 \(10^7\)。

对于 \(30\%\) 的数据,保证答案不超过 \(2.5\times 10^{8}\)。

对于 \(40\%\) 的数据,保证答案不超过 \(7\times 10^{9}\)。

对于 \(50\%\) 的数据,保证答案不超过 \(2.5\times 10^{11}\)。

对于 \(60\%\) 的数据,保证答案不超过 \(3.5\times 10^{14}\)。

对于 \(70\%\) 的数据,保证答案不超过 \(1.5\times 10^{16}\)。

对于 \(80\%\) 的数据,保证答案不超过 \(7\times 10^{17}\)。

对于 \(90\%\) 的数据,保证答案不超过 \(3.5\times 10^{30}\)。

对于 \(100\%\) 的数据,保证答案不超过 \(10^{200}\)。

每一组数据的时限为 \(1\) 秒。

金秋重聚模拟赛

未参加
状态
已结束
规则
OI
题目
4
开始于
2017-10-07 18:00
结束于
2017-10-07 22:00
持续时间
4.0 小时
主持人
参赛人数
425