[Softeer/소프티어][level3] 수퍼바이러스 (C++)

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=391&sw_prbl_sbms_sn=18559

Softeer

 

 

[난이도] level3
[유형] 분할정복

[풀이]
N 제한이 굉장히 크기 때문에 일일이 계산해주면 안되고 재귀함수를 이용한 분할정복을 해주어야 합니다.

 

#include <cstdio>
using ll = long long;
ll K,P,N,mod=1000000007;
ll sol(ll n){
    if(n==1) return P;
    ll ret = sol(n/2);
    ret=(ret*ret)%mod;
    if(n%2) ret=(ret*P)%mod;
    return ret;
}
int main(){
    scanf("%lld%lld%lld",&K,&P,&N);
    printf("%lld",(sol(N*10)*K)%mod);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/수퍼바이러스.cpp