/ 基本思想:
* 如果 N=a1^k1 * a2 ^ k2 * … an ^ kn
* 约数个数: (k1+1) * (k2+1) * … (kn+1)
* 约数之和: (a1^0 + a1^1 + … + a1^k1) * … * (an^0 + an^1 + … + an^kn)
* 欧拉函数 n * (a1 - 1)/a1 * (a2 - 1)/a2 * … * (an - 1)/an
/
算法1
import java.util.*;
public class _873_欧拉函数 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
for(int j=0;j<n;j++) {
int a=sc.nextInt();
int r=a;
for(int i=2;i<=Math.sqrt(a);i++) {
if(a%i==0) {
while(a%i==0) {
//一次性消除全部的i
a/=i;
}
r=r/i*(i-1);
}
}
if(a>1) {
r=r/a*(a-1);
}
System.out.println(r);
}
}
}