글 읽기 - 시간초과,도와주세요(소스가 조금 읽기 불편하거나 힘들 수 있습니다)

sg1774 7년 전 0

어떤 부분이 사간초과가 나나요?

#include <stdio.h>

int main()
{
    long long a,b,c,d;
    scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
    long long i,f=a,g=b,h=c,j=d;
    for(i=0;g!=j;i++){
        if(g<j){
            f+=a;
            g+=b;
        }
        else{
            h+=c;
            j+=d;
        }
    }
    f+=h;
    for(i=f;i>0;i--){
        if(f%i==0&&g%i==0){
            f/=i;
            g/=i;
            break;
        }
    }
    printf("%lld %lld",f,g);
    return 0;
}

zych1751 7년 전 0

이러한 인풋에 대해서

29946 29947
29958 29959

이런 답을 출력해야합니다.

1794304440 897182173

덧셈으로 저 정답을 뽑아내기 위해서는 시간이 매우 오래걸릴 것 같습니다.

최대공약수, 최소공배수를 이용해서 분수계산을 좀 더 빠르게 해야합니다.

sg1774 7년 전 0

그렇군요! 근데 그러면 다른 소스도 좀 봐주실 수 있나요? 이것도 시간초과가 났어요ㅠㅠ

#include <stdio.h>

int main()
{
    long long a,b,c,d;
    scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
    long long i,f=a,g=b,h=c,j=d,s;
    g<j? s=g:s=j;
    for(i=s;i>1;i--){
        if(g%i==0&&j%i==0){
            g/=i;
            j/=i;
            break;
        }
    }
    h*=i*g;
    g*=i*j;
    f*=i*j;
    f+=h;
    for(i=f;i>0;i--){
        if(f%i==0&&g%i==0){
            f/=i;
            g/=i;
            break;
        }
    }
    printf("%lld %lld",f,g);
    return 0;
}

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

문제

문제

출처

ICPC

시간초과,도와주세요(소스가 조금 읽기 불편하거나 힘들 수 있습니다)

sg1774 7년 전 0

zych1751 7년 전 0

sg1774 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말