欧拉函数
测试数据来自 system/2025
描述
欧拉函数 \(\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\) 秒。
信息
- ID
- 1020
- 难度
- 10
- 分类
- (无)
- 标签
- (无)
- 递交数
- 1
- 已通过
- 0
- 通过率
- 0%
- 上传者