[Softeer] 바이러스 (C++)

O(N) 문제

#include<iostream>

using namespace std;

int main(int argc, char** argv)
{
	unsigned long K, P, N;

	scanf("%u %u %u", &K, &P, &N);

	for(unsigned int i=0; i<N; i++){
		K *= P;
		K %= 1000000007;
	}

	printf("%lu", K);
	return 0;
}

 

1 ≤ K ≤ 108인 정수, 1 ≤ P ≤ 108인 정수, 1 ≤ N ≤ 106인 정수 제약조건이 있는데, N번 만큼 K *= P 연산을 끝낸 후에는 수가 unsigned long long보다 커질 수 있다. 최종 결과는 1000000007로 나눈 나머지를 구한 값이기 때문에 연산을 수행할 때마다 K를 1000000007로 나눈 나머지 값으로 업데이트해주면 큰 수에 대한 문제를 고려하지 않고 문제를 해결할 수 있다.

 

나머지가 q라 할 때  매 번 (A*B) % q를 수행하는 것이므로 q로 나눈 나머지를 A=aq + r1, B=bq + r2이라 해보자.

그렇다면 A * B = abq^2 + aqr2 + bqr1 + r1r2

이때 abq^2 + aqr2 + bqr1 에는 모두 q가 있으므로 몫에 해당하고, 남은 r1r2에 q를 나눈 나머지는 r1r2 % q가 된다. 

따라서 (A*B) % q 결과 나머지는 r1r2 % q와 동일하므로 (K * P) % 1000000007를 N번 수행하면 된다.