[BOJ 1629:乗算]

中に入る.
巴金督の復学ビデオを見て、この問題が出てきて、私は勉強を始めました.
実際,ルールとモジュール化算術演算の特徴を知るだけで簡単に再帰的に実現して解決できる問題であるため,その規則性を記録したい.
問題の説明

これは簡単にA^B%Cを求める問題です.
ただし、範囲はintの最大範囲であるため、範囲はMath.pow(a, b) % cだけではない.
bの最大範囲が小さい場合

int val = 1;
for(int i = 0; i < b; i++) {
  val = (val*a) % c;
}

使えますが、21億回は必ずタイムアウトします.
では、この問題をどう解決すればいいのでしょうか.
ルールの説明
まず,モジュール化算術演算の特徴を理解することは容易である.
a^2 % c = {(a%c) * (a%c)} % c

この絵を見るのは少し簡単だと思います.
最も重要なのは、手で一つ一つ計算して、それに従うと、もっと理解できます.
では、ここで奇数乗の剰余値はどのように求めますか.
求め終わったらAにもう一度乗じて、残りを求めればいいです.
これらの方法とモードを適用し,時間複雑度はO(logb)であった.
コード#コード#

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();

		System.out.println(recursion(a, b, c));
	}

	static long recursion(int a, int b, int c) {
		if(b == 1)
			return a%c;
		
		long val = recursion(a, b/2, c);
		val = (val*val) % c;
		
		if(b%2 == 0)
			return val;
		else
			return (val*a) % c;
	}
}

実は最初はval = (val*val) %cをval = (val*a) % cに変更しました.
そうなると平方の数は1/2ですが、実際に残りの値を乗算するのは平方ではなく、一度だけ乗算すると計算が間違ってしまいます.
次にvalのデータ型をintに変更します.残りの値valは2乗され、intの範囲を超えているのでlongに変更します.
おしゃべり
モジュール化算術演算の特徴を理解するために、少し分けて、
このようにしても忘れません.