글 읽기 - 유클리드 알고리즘 관련문제.

kimsy96 5년 전 0

구간과 비교할 수를 입력한 후 그입력한 수와 구간사이의 서로소의 개수를 구하는 문제입니다.

잘알려진 유클리드함수를 썼고 리턴값이 1일때 마다 count해줘서 그 count를 출력했습니다.

구현은 쉬웠는데 정답률이 낮아서 느낌이 이상했는데 결국 틀렸네요.

어디서 잘못됬을까요

#include <stdio.h>

int Euclidean(int a, int b)
{
	return a%b ? Euclidean(b, a%b) : b;
}


int main(void)
{
    int n;
    scanf("%d",&n);
    int A,B,N;
    int i;
    int count;

    int j=1;
    while(n--)
    {
        count=0;
        scanf("%d %d %d",&A,&B,&N);
        for(i=A;i<=B;i++)
        {
            if(Euclidean(N,i)==1)
                count++;
        }
        printf("Case #%d: %d\n",j,count);
        j++;


    }
    return 0;





}

chogahui05 5년 전 1

A, B, N이 주어진다. (1<= A <= B <= 10^15)

당연한 이야기겠지만. int형을 쓰면 안 되겠지요?

구현은 쉬운데 정답률이 낮은 경우에는 90% 이상은 이 경우라고 생각하시면 편합니다.

무식하게 구현하면 답은 맞는데 시간 초과가 나는 경우.

이 문제가 딱 그 꼴입니다. 다시 풀어보세요.

kimsy96 5년 전 0

범위를 잘못봤네요..;

고쳤더니 타임오버가 나긴했지만

어째든 감사합니다.

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

문제

문제

출처

ICPC

유클리드 알고리즘 관련문제.

kimsy96 5년 전 0

chogahui05 5년 전 1

kimsy96 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말