글 읽기 - 채점 96%에서 시간초과가 뜹니다..

steve11344 6년 전 0

제가 생각했을때, 최악의 경우 a= 2^31-1, b= 2^31, c=2^31 일때,

대충 logb+log31 정도 연산을 한다고 생각합니다. -> 30+5 정도

근데 왜 시간초과가 뜨는지 모르겠습니다 ㅠㅠ 도와주십쇼

#include <cstdio>
#include <cmath>
#define ll long long
using namespace std;
int main() {
    ll a,b,c,ans =0,tmp=1,tt=1;
    scanf("%lld %lld %lld",&a,&b,&c);
    ans = a;
    while(1){
        ans = ans%c;
        if(c-ans < ans) ans = -(c-ans);
        tt = ans;
        if(b%2 ==0){
            b/=2;
        }
        else{
            b = (b-1)/2;
            tmp *= tt;
            tmp %= c;
        }
        ans = (ans*ans)%c;
        if(b==1) break;
    }
    ans = (ans*tmp)%c;
    if(ans < 0) printf("%lld\n",c+ans);
    else printf("%lld\n",ans);
    return 0;
}

chogahui05 6년 전 2

그러게요. 96%에서 시간초과 나거나 틀렸습니다가 뜨면 화가 많이 나죠.

다 풀었는데.. 저도 그런 적 많습니다.

왜 그럴까요?

저도 잘 못 찾겠는데요. 이 테스트 케이스 한 번 넣어보시면 어떤 결과가 나오나요?

/*
1000000000 1 234234125
*/

steve11344 6년 전 0

정말 감사합니다.

제 코드에서 while문 들어가는 조건이 b >=2 일때만 해당되더라구요

그래서 b=1일때는 무한루프를 돌아서 시간초과가 났내요 ㅠㅠㅠ 간단한 실수인데...

감사합니다!

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

문제

문제

출처

ICPC

채점 96%에서 시간초과가 뜹니다..

steve11344 6년 전 0

chogahui05 6년 전 2

steve11344 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말