글 읽기 - 시간초과 해결을 어떻게 해야할까요?

yjkim9591 1년 전 0

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

b의 최대 범위가 2,147,483,647이니까 0.5초면 0.5억인 걸로 알고 있는데,
아래 루프에서는 최소 b번은 루프를 돌려야하는데

시간을 줄일만한 방법을 생각해보면
아래 루프를 7번줄에 a를 a^5로 바꾸고,6번줄에 b->b/5로 바꾸면
a를 곱할때 범위가 longlongint를 넘어가서 안됩니다.

어떻게하면 시간복잡도를 더 줄일 수 있을까요?

#include <stdio.h>

int main(){
    long int a,b,c,temp=0,mul=1;
    scanf("%ld %ld %ld",&a,&b,&c);
    for(int i=0;i<b;i++){
        mul*=a;
        if(mul>c){
            mul%=c;
        }
        if(temp==mul) break;
        else temp=mul;
    }
    printf("%ld",temp);
    return 0;
}

seawon0808 1년 전 0

분할 정복을 이용한 거듭제곱에 대해서 검색해 보세요.

byeongkeunahn 1년 전 0

Exponentiation by squaring이라고 하는데 A^1 mod C, A^2 mod C, A^4 mod C, A^8 mod C, A^16 mod C, ...을 계산한 뒤 B의 이진법 표현에 따라 적절한 항을 선택하여 곱해주는 방법이 있습니다.

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

문제

문제

출처

ICPC

시간초과 해결을 어떻게 해야할까요?

yjkim9591 1년 전 0

seawon0808 1년 전 0

byeongkeunahn 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말