- 主页/
- 赛码网 周考 4.28 第二题要怎么优化才能AC啊
一直50%。。。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int n = scanner.nextInt();
int num=1;
if(n==1){
System.out.println(1);
}else if(n%2!=0){
for(int i=n/3+2;i<n;i=i+2){
if(!solve(i,n)){
num++;
}
}
System.out.println(num+n/2);
}else {
System.out.println(n/2);
}
}
scanner.close();
}
public static boolean solve(int m,int n){
while (n%m != 0) {
int temp = n%m;
n=m;
m= temp;
}
if(n!=1) return true;
return false;
}
}
我的67%
#include<stdio.h>
int main(){
long int n,count=0,i,t,k,c;
scanf("%ld",&n);
if(n==1)printf("%ld",count+1);
else{
for(i=1;i<n;i++){
t=i;
k=n;
while(k%t!=0){//欧几里得算法（最大公约数为1，两数互质）
c=k;
k=t;
t=c%t;
}
if(t==1) count++;
}printf("%ld",count);
}
return 0;
}
isaimawang
@ 赛码网
533869549