1044: 【模板】单点欧拉函数

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:75 Solved:46

Description

给定一个整数$n$,求欧拉函数: $$\phi(n) = n \times \prod_{p \in prim,\space p | n}(1-\frac{1}{p})$$ 特别地,$\phi(1) = 1$。 ### 输入格式 第一行一个整数$T$,表示样例个数。$(1 \le T \le 100)$ 一个整数$n$。$(1 \le n \le 10^{12})$ ### 输出格式 每一行对应一个样例,一个整数表示答案。 ### 样例输入1 ``` 2 10 5 ``` ### 样例输出1 ``` 4 4 ```