[PS規格-4.2]1629号:乗算

問題情報

白駿1629号-ショートカット 難易度：シルバー1 アルゴリズム:分割征服

コメント

この問題は10回も間違っていて、うんざりしている.A,B,CA,B,CA,B,Cは2147483648364672147483647以下の自然数であり,一般的な繰返し二乗では問題を解くことはできない.この問題はブログの助けで始まったので、考え自体が近づきやすいです.指数を半分に分けて、最後に合わせて解けばいいです.しかし、彼を10回間違えた主犯は、残りの演算のためだ.計算中に余剰演算を行うとint型とみなされることが多く,値にばらつきが生じる.値をlong long intインチに保持し、残りの演算を1回行った後、平方の値に残りの演算を1回行えば問題を解決できます.

分割征服関数−Base CaseがB=0,B=1の場合。このとき0とAをそれぞれ出力すればよい。 指数が偶数であれば2で割った値を指数に代入し、再帰的に呼び出す。偶数であれば、1を引いた指数を偶数の値に代入し、再帰的に呼び出す。この場合は上記のように残りの演算を適切に行います。

ソースコード

#include <iostream>
#include <cmath>

using namespace std;

long long int divideConquer(long long int A, long long int B, long long int C) {
    if (B > 1) {
        if (B % 2 == 0) {
            long long int x = divideConquer(A, B / 2, C);
            x %= C;
            return (x * x) % C;
        }
        else
            return divideConquer(A, B - 1, C) * A; // 짝수로
    }
    else if (B == 1){
        return A;
    }
    else if (B == 0) {
        return 1;
    }
}

int main() {
    int a, b, c;
    cin >> a >> b >> c;

    cout << divideConquer(a, b, c) % c; 
}