백준 13171 A C++

https://www.acmicpc.net/problem/13171

13171번: A

---

문제

음이 아닌 두 정수 A, X 가 있을 때 A^X을 구하는 방법을 생각해보자. 물론 이 수는 매우 클 수 있기에, 1,000,000,007 (= 109 + 7)로 나눈 나머지를 구할 것이다. a mod x를 a를 x로 나눴을 때의 나머지라고 표현하면,

(a × b) mod x = {(a mod x) × (b mod x)} mod x

가 성립하기 때문에, 어떤 두 정수를 1,000,000,007로 나눈 나머지만 알고 있어도 그 두 정수의 곱을 1,000,000,007로 나눈 나머지를 쉽게 계산할 수 있다.

본 문제로 돌아가서, 그렇다면 이제 A를 X 번 곱하면 AX을 쉽게 구할 수 있을 것 같아 보인다. 그러나 안타깝게도 X가 상당히 커서 64비트 정수의 범위에 있다면 A를 하나하나씩 곱하는 방식으로는 상상할 수 없을 정도로 긴 시간이 흘러야 답을 찾을 수 있을 것이다. 그래서 다음과 같이 곱셈의 횟수를 줄이는 방법을 사용한다.

1. 먼저 A1, A2, A4, A8, ...을 순서대로 계산한다. 각 수는 이전에 있는 수를 제곱함으로써 계산할 수 있고, 지수가 X 를 딱 넘지 않을 시점까지만 계산하면 충분할 것이다. X가 64비트 정수의 범위에 있으므로 계산하는 수는 64개보다 작을 것이다.
2. 이제 X 를 이진수로 나타내 보자. 예를 들어 X를 11로 두면, X = 11 = 1 + 2 + 8이다. 그런데 지수법칙에 의해, A11 = A1+2+8 = A1 × A2 × A8이 성립한다. 이를 통해 1번 단계에서 미리 계산해 놓았던 수 몇 개만 곱해서 AX 을 계산할 수 있음을 알 수 있다.

즉, 차례로 A를 곱해 나간다면 시간이 X에 비례하게 걸리겠지만, 위의 방법을 이용하면 시간이 log(X)에 비례하게 걸리게 된다. AX를 구하는 프로그램을 작성하라.

---

입력

첫 번째 줄에는 정수 A(1 ≤ A ≤ 1018)이 주어진다.

두 번째 줄에는 정수 X(1 ≤ X ≤ 1018)가 주어진다.

---

출력

A^X을 출력한다. 이 수는 매우 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력해야 한다.

---

일단 이 문제는 거듭제곱에 관한 문제입니다. A^X(A의 X제곱을 구해야 하는 것이 목적입니다.)

먼저 X제곱이 1일 때를 생각해보면, 어떤 수의 1제곱은 어떤 수 그 자체입니다. A^1 = A

그리고 X제곱이 0일때를 생각해보면, 어떤 수의 0제곱은 1입니다 A^0 = 1

 

그리고 X제곱이 홀수 , 짝수 일때를 생각해 본다면 A의 X제곱은 X가 짝수 일때,

A^x/2 * A^x/2라고 할 수 있습니다.

A가 10이고 x가 6이라면 10^6 = 10^3 * 10^3 이 성립하며, 10^6을 다 구하지 않고

짝수 일때  10^3을 구하고 이를 두 번 곱합니다.

 

즉, A^X(X가 짝수)일떄 A^X = A^x/2 * A^x/2가 성립합니다.

 

이제 X가 홀수 일때의 경우입니다.

X가 홀수일 때에는 다음과 같은 표현이 성립합니다.

A^X (X는 홀수) = A^X-1 * A

A가 10이고 X가 9라고 생각해본다면 , 10^9 = 10^8 * 10 이 성립하고, X가 홀수 일 경우,

 

A^X = A^X-1 * A가 성립합니다.

 

처음에 알고리즘은 맞는데 왜 틀릴까 생각하다가 글을 남겼는데, 미쳐 파악하지 못한 부분이 있었습니다.

 

제일 처음 작성한 코드 ->

//처음 코드

#include <iostream>
#define MOD 1000000007
using namespace std;
typedef long long ll;
 
ll calculate(ll a,ll x){
    if(x == 0){
        return 1;
    }
    else if(x == 1){
        return a;
    }
    else if(x%2 != 0){
        return calculate(a,x-1) % MOD * a % MOD;
    }
    else if(x%2 == 0){
        return calculate(a,x/2) % MOD * calculate(a,x/2) % MOD;
    }
}
int main(void){
    ll A;
    ll X;
    cin >> A >> X;
    /*나머지 연산 X */
    cout << calculate(A,X) % MOD;
}

 

 

제가 쓴 코드와 다른 분들의 코드를 비교해보니, 제일 처음 거듭제곱 구하는 함수를 호출할 떄 다른분들은 A에 

나머지 연산  1,000,000,007을 하여서 질문을 남겼고, 답변이 달렸습니다.

 

다른 분들의 코드 -> 함수 호출시 나머지 연산을 한 코드

#include <iostream>
#define MOD 1000000007
using namespace std;
typedef long long ll;
 
ll calculate(ll a,ll x){
    if(x == 0){
        return 1;
    }
    else if(x == 1){
        return a;
    }
    else if(x%2 != 0){
        return calculate(a,x-1) % MOD * a % MOD;
    }
    else if(x%2 == 0){
        return calculate(a,x/2) % MOD * calculate(a,x/2) % MOD;
    }
}
int main(void){
    ll A;
    ll X;
    cin >> A >> X;
    
    /*나머지 연산을 처음에 해야 하는 이유..? */
    cout << calculate(A % MOD,X) % MOD;
}

 

감사합니다..

제일 큰 문제는 오버플로우 문제 였습니다. 

* 곱하기와 % 나머지는 연산자 우선순위가 같습니다.  즉, 괄호가 없다면 왼쪽에서 오른쪽으로 계산이 진행됩니다.

 

제가 작성한 코드 중

 calculate(a,x-1) % MOD * a % MOD

이러한 코드가 있는데, 이는 괄호가 없으니 % -> * -> %순으로 왼쪽에서 오른쪽으로 계산됩니다.

이떄 calculate(a,x-1) % MOD는 MOD미만의 수가 확실하지만, 그 후 a를 곱하는 코드에서 a가 굉장히 큰 수라면

(이 문제에서는 10^18) 오버플로우가 발생 할 수 있습니다.

 

그래서 계산식에 괄호를 적절히 쳐서 오버플로우를 해결 할 수 있었습니다..!

---

개선된 전체 소스 코드 ->

#include <iostream>
#define MOD 1000000007
using namespace std;
typedef long long ll;
 
//괄호를 계산 과정마다 쳐줘서 오버플로우를 벗어나게 

ll calculate(ll a,ll x){
    //거듭제곱을 구하는 재귀 함수
    
    if(x == 0){ //x가 0이라면 1리턴 A^0 = 1
        return 1;
    }
    else if(x == 1){ //x가 1이라면 A리턴 A^1 = A
        return a;
    }
    else if(x%2 != 0){ //x가 홀수라면 A^x-1 * A
        return (calculate(a,x-1) % MOD) * (a % MOD);
    }
    else if(x%2 == 0){ //x가 짝수라면 A^x/2 * A^x/2
        return (calculate(a,x/2) % MOD) * (calculate(a,x/2) % MOD);
    }
}
int main(void){
    ll A;
    ll X;
    cin >> A >> X;
    cout << calculate(A,X) % MOD;
}