はじめに

AtCoder Typical Contest(ATC) とは、競技プログラミングにおける、典型問題を出題するコンテストです。
AtCoder さん、ありがとうございます。

今回のお題

AtCoder Typical Contest 002 B - n^p mod m

今回のテーマ、繰返し二乗法

Ruby

例えば、2 の 64 乗を求める場合、単に 2 を掛けるのであれば 63 回掛け算が必要ですが、計算結果を利用することにより 6 回の掛け算で求めることができ、計算の高速化につながります。

2^64.rb

n = 2
63.times do
  n *= 2
end
puts n # => 18446744073709551616

n = 2
6.times do
  n *= n
end
puts n # => 18446744073709551616

これを奇数乗や除数にも適応したのが、繰返し二乗法になります。

ruby.rb

n, m, p = gets.split.map(&:to_i)
def mpow(n, p, mod)
  r = 1
  while p > 0
    r = r * n % mod if p & 1 == 1
    n = n * n % mod
    p >>= 1
  end
  r
end
puts mpow(n, p, m)

関数化しておけば、後々のコンテストにも~~コピペ~~使用できます。

Python

python.py

n, m, p = map(int, input().split())
def mpow(n, p, mod):
    r = 1
    while p > 0:
        if p & 1 == 1:
            r = r * n % mod
        n = n * n % mod
        p >>= 1
    return r
print(mpow(n, p, m))

後置 if はもう少し勉強してからになります。

Perl

perl.pl

chomp (my ($n, $m, $p) = split / /, <STDIN>);
sub mpow {
  my ($n, $p) = @_;
  my $r = 1;
  while ($p > 0) {
    $r = $r * $n % $m if $p & 1;
    $n = $n * $n % $m;
    $p >>= 1;
  }
  $r;
}
print mpow($n, $p), "\n";

Perl の場合、$m のスコープでエラーにならないようです。

Java

java.java

import java.math.BigInteger;
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        BigInteger n = new BigInteger(sc.next());
        BigInteger m = new BigInteger(sc.next());
        BigInteger p = new BigInteger(sc.next());
        sc.close();
        System.out.println(n.modPow(p, m));
    }
}

Java には BigInteger クラスに modPow メソッドがあります。

	Ruby	Python	Perl	Java
コード長	183 Byte	217 Byte	227 Byte	386 Byte
実行時間	7 ms	17 ms	3 ms	106 ms
メモリ	1788 KB	3060 KB	640 KB	24020 KB

まとめ

ATC 002 B を解いた
Ruby に詳しくなった
Python に詳しくなった
Perl に詳しくなった
Java に詳しくなった