/ Vijos / 题库 /

欧拉函数

欧拉函数

描述

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

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

格式

输入格式

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

输出格式

输出一个正整数,表示最小满足条件的 nn

样例1

样例输入1

1 2

样例输出1

样例2

样例输入2

2 5

样例输出2

12

限制

对于 20%20\% 的数据,保证答案不超过 10710^7

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

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

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

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

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

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

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

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

每一组数据的时限为 11 秒。

信息

ID
2025
难度
7
分类
(无)
标签
(无)
递交数
187
已通过
30
通过率
16%
被复制
5
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

金秋重聚模拟赛