アルゴリズムチャレンジ-8

1629乗算

質問する

自然数AにBを乗じた数を知りたいです.ただし、購入したい数が非常に大きい場合がありますので、残りの数を求めるためにCに分けるプログラムを作成してください.

入力

1行目A,B,Cはスペースを隔てて順次与えられる.A,B,Cともに2147483647以下の自然数である.

しゅつりょく

出力1行目AにBを乗じた数をCの余剰数で割る.

入力例

10 11 12

サンプル出力

4

コード#コード#

import java.util.*;

public class Main {

    public static long C;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long A = scanner.nextLong();
        long B = scanner.nextLong();
        C = scanner.nextLong();

        System.out.println(multiple(A,B));
    }

    public static long multiple(long A, long B){
        if(B==1){
            return A%C;
        }

        long temp = multiple(A,B/2);

        if(B%2==1){
            return (temp*temp%C)*A%C;
        }
        return temp*temp%C;
    }
}