글 읽기 - 시간 초과를 어떻게 해결할까요;;

kevink1113 4년 전 0

오일러 파이를 이용해서 빠르게 서로소의 개수를 구할 수 있다는 것을 알고 아래와 같이 구현해 보았는데 시간초과가 뜨네요;;

더 최적화하는 과정이 필요한가요?

#include <stdio.h>
int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a%b);
}
int getEulerPhiFunc(int n){
    int cnt = 0;
    for(int i = 1; i < n; i++){
        if(gcd(n, i) == 1) cnt++;
    }
    return cnt;
}

int main(){
    int in;
    while(1){
        scanf("%d", &in);
        if(in==0) return 0;
        printf("%d\n", getEulerPhiFunc(in));
    }
    
    return 0;
}

hunni10 4년 전 1

제가 부족하지만 생각해본거는..

1. 재귀대신 반복으로 구현한다

2.i 와 n이 서로소가 아니라면, i의 배수들은 모두 서로소가 아니다.

예를들어 16은 2와 서로소가 아니므로, 4, 6, 8, 10..은 직접 구하지 않고 서로소가 아님을 알 수 있음

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간 초과를 어떻게 해결할까요;;

kevink1113 4년 전 0

hunni10 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말