[PS] 백준 13171번: A

|

문제

내가 이해한 문제 내용

A의 X승을 구하는데 A와 X가 매우 크고($10^{18}$) $A^X$도 매우 크기 때문에 1000000007로 나눈 나머지를 계산하라는 문제, 캐싱하는 방식을 사용하라는 조건.

접근 방식

2의 N승 방식으로 캐싱을 한 다음 X를 이진수로 바꾸는 계산해서 캐싱한 값을 이용하였다.

어려웠던 점 & 배운 점

처음 캐싱할 때 말도 안되게 인덱스를 2의 N승으로 설정해서 런타임 에러가 났고 그 다음엔 들어올 수 있는 최댓값이 10^18이라는 것을 간과하고 그 값엔 모듈러를 취하지 않았었다;;

시간복잡도

$2^n \le x$를 만족할 동안 반복하기 때문에 $n\le log_2{x}$가 된다. 따라서, $O(log_2{x})$

코드

#include <cstdio>

typedef long long ll;

ll a,x,ans,i,j;
const ll mod = 1000000007;
ll cache[65];

int main(void)
{
    scanf("%lld%lld",&a,&x);
    cache[1] = a%mod;
    i=2,j=2;
    while(i<=x){
        cache[j] = cache[j-1]*cache[j-1];
        cache[j] %= mod;
        i*=2,j++;
    }

    ans=1,i=1,j=1;
    while(x){
        ans *= (x%2 ? cache[j] : 1);
        ans %= mod;
        x/=2,i*=2,j++;
    }
    printf("%lld",ans);
    return 0;
}