学習記録：Java：A29 - Power , 競技プログラミングの鉄則 演習問題集

はじめに

Javaで解答例を書いています。自分用のメモです。問題としては、競技プログラミングの鉄則　演習問題集 の　A29 - Power という問題です！○○乗を素早く計算するアルゴリズムが使われています！あとは、割り算の余りの性質を使っていますね。

問題のポイントと自分がミスったポイント

問題のポイント

• ○○乗って分解できますよね。5乗なら1乗と4乗に。高校の時に習った指数法則。

ミスしたポイント

• if ((b / wari) % 2 == 1)の意味が分からなかった。2のi乗の時に、二進数に直したときに1になっているポイントでanswerに2のi乗を掛け合わせるために用意していたんだなー。

目次

問題と公式の解答例

問題 A29 - Power

A29 - Power , https://atcoder.jp/contests/tessoku-book/tasks/math_and_algorithm_aq

公式の解答例

https://github.com/E869120/kyopro-tessoku/blob/main/codes/java/chap05/answer_A29.java

解答例

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();

        System.out.println(Power(a, b, 1000000007));
    }

    static long Power(long a, long b, long m) {

        long p = a;
        long answer = 1;
// n が 30 未満なのは問題の制約から
// 制約に応じて変える必要アリ
        for (int i = 0; i < 30; i++) {
// 計算を2進数で考えよう
            int wari = (1 << i);
// bを2進数で表したとき、1になっているところでpをかけるよ
            if ((b / wari) % 2 == 1) {
                answer = (answer * p) % m;
            }
// pのi乗を計算
            p = (p * p) % m;
        }

        return answer;
    }
}