/ OIer TK / 题库 /

Euler

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
通过率
?
上传者