문제

자연수 A를 B번 곱한 수를 C로 나눈 나머지를 구하시오
a,b,c는 모두 2,147,483,647이하의 자연수이다.

풀이

int형의 범위가 -2,147,483,647~2,147,483,647이므로 A,B,C는 모두 int 형으로 둘 수 있음

풀이 1 - 시간초과

#include <bits/stdc++.h>
using namespace std;
long long tmp;

void multiplication(long long a, int b, int c){ //10 11 12
    if(b==0) {cout << a; return;}
    a*=a; a%=c; b--;
    multiplication(a, b, c);
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long a;
    int  b, c;
    cin >>a>>b>>c;
    
    multiplication(a, b, c);
    
    return 0;
}

재귀를 사용해서 푸는 문제 아닌가...? 왜 시간초과가 떴을까?
long long끼리 곱하는 연산 때문인가??

a값이 변경되는 곳에서 문제가 생겼다. 원래 의도한 풀이는 10X10, 10X100 이렇게 되어야 하는데 위의 코드대로 실행을 시키면 10 X10, 100 X 100, 1000 X 1000 이렇게 변하는 문제가 있었다. 이를 해결하기 위해서 tmp 변수를 넣었다.
그래도 안된다!
b번 곱하는 것이라면 시간복잡도가 O(N)이 나온다.
O(N)으로 풀어도 안되나..?

풀이 2 - 분할 정복

이 문제에는 두가지 문제점이 있다.
1. 숫자의 범위가 자료형의 표현 범위보다 커진다.
2. O(n)의 시간복잡도로 문제를 풀어도 시간제한에 걸린다.

1번은 연산을 할 때마다 c로 나누어서 해결이 가능하다. 2번은 분할 정복으로 해결이 가능하다.

long long pow(long long a, long long b, long long c){ //10 11 12
	if(b==1) return a%m;
    long long val = pow(a, b/2, m);
    val = val*val%m;
    if(b%2==0) return val; //b가 짝수이면 그냥 반환
    return val*a%m; //홀수이면 한번 더 곱하고 나눠서 반환
 }

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll POW(ll a, ll b, ll m){
  if(b==1) return a % m;
  ll val = POW(a, b/2, m);
  val = val * val % m;
  if(b%2 == 0) return val;
  return val * a % m;
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  ll a,b,c;
  cin >> a >> b >> c;
  cout << POW(a,b,c);
}

b를 짝수일때, 홀수일때로 나누어서 생각한다. 2^10이면 b가 짝수인데, 2^10 = 2^5x2^5이고 2^5 = 2^2x2^2x2이고 2^2 = 2X2이다. 이를 생각해보면 b를 계속 2를 나누어 연산하게 되고, 연산한 값을 변수에 저장하고 계산하면 시간 복잡도는 O(logn)이 된다. (n==b)