题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
package com.rainco;
import java.util.*;
public class Main {
static int n;
static int N=100010;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
for(int k=1;k<=n;k++){
int a=sc.nextInt();
//不用打印素数表 类似筛选法
int temp=a;
long ans1=a;
long ans2=1;
for(int i=2;i*i<=a;i++){
if(temp%i==0){
while (temp%i==0){
temp/=i;
}
ans1*=i-1;
ans2*=i;
}
}
if(temp>1){
ans1*=temp-1;
ans2*=temp;
}
System.out.println(ans1/ans2);
}
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla