[Softeer] 수퍼바이러스

문제링크 : https://softeer.ai/practice/info.do?idx=1&eid=

시간복잡도 : O(N) but N이 10^16...!!

#include <iostream>

using namespace std;

int powerTen(int start, int p)
{
	int ans = start;
	for (int i = 0; i < 10; i++)
		ans *= p;
	return ans;
}

int main()
{
	int K, P;
	long long N;
	cin >> K >> P >> N;

	// P의 N승 * K
	int ans = 1;
	for (long long i = 0; i < N; i++)
	{
		ans = powerTen(K, P);
	}
	cout << ans;

	return (0);
}

시간복잡도 : O(logN)

#include <iostream>
#define MOD 1000000007
typedef long long ll;
using namespace std;

ll calc(ll base,ll time)
{
	if (time == 1) return base;
	ll result = calc(base, time / 2);
	result = (result * result) % MOD;
	if (time % 2)
		result = (result * base) % MOD;
	return result;
}

ll getVirus(ll start,ll base, ll expo)
{
	return ((start * calc(base, expo * 10)) % MOD);
}

int main()
{
	ll K, P, N;
	cin >> K >> P >> N;

	// P의 N승 * K
	cout << getVirus(K, P, N);
	
	return (0);
}