Euler
测试数据来自 system/1862
描述
欧拉函数 φ(n) 定义为不超过正整数 n 并且与 n 互素的整数的数目。
可以证明,
φ(n) = n ∗ ∏ ( (pi-1)/pi )
其中pi为n的全部素因子。
已知 y,求最小的自然数 x 使得 φ(x) = y.
多组询问。
格式
输入格式
第一行,一个整数 T,表示多少组询问。
接下来 T 行,每行一个整数 yi。保证有解。
输出格式
输出 T 行,每行一个整数,依次表示每次询问的答案。
样例1
样例输入1
4
10
2
104
8800440
样例输出1
11
3
159
8809079
限制
30% 的数据:1 <= y <= 10^6.
60% 的数据:1 <= y <= 10^9.
100% 的数据:1 <= y <= 10^12,1 <= T <= 2.
提示
前 20 个正整数的欧拉函数值依次是 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8.
来源
BJOI 2014 Day 1
信息
- ID
- 1795
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者