곱셈

일단 이문제 시간제한이랑 최대, 최소보고

for문 사용하면 안된다라는 점과

시간복잡도를 O(log n)으로 줄여야 한다는 것 까지는 이해를 함.

그리고 나머지 연산을 해야하기는 해야할거같은데 뭐 우째야 될지를 모르겠었음.

나머지 연산 특징 ❗❗❗

(A + B) % p = ((A % p) + (B % p)) % p
(A * B) % p = ((A % p) * (B % p)) % p
(A - B) % p = ((A % p) - (B % p) + p) % p

20억 X 20억 해버리면 long long으로도 커버가 안됨.

그래서 위에 모듈연산자 특징을 사용해서

곱할 때마다 % C 이렇게 해준다.

몰랐던 부분 👍

나머지 연산자의

(A * B) % C = A % C * A % C

이부분 몰랐다...

이게 되기 때문에 곱할 때마다 나머지 연산자 연산을 수행을 해준다. 재귀함수랑 함께..

코드 분석

2^8은 2^4 * 2^4이다.

따라서 분할정복을 하며 O(log n)으로 풀어야함.

log n 이 될려면 반씩 줄여나가야 함.

#include <iostream>
#include <stack>
using namespace std;
#define endl "\n"
typedef long long ll;

int a, b, c;

ll go(ll a, ll b)
{
	if (b == 1) return a % c;
	
	ll ret = go(a, b / 2);
	ret = (ret * ret) % c;
	if (b % 2) ret = (ret * a) % c;
	return ret;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> a >> b >> c;
	cout << go(a, b) << endl;
	
	return 0;
}

반씩 줄여가는 부분이

ll ret = go(a, b / 2);이 부분이다.

b / 2하는 부분