Perl で学ぶ剰余計算

はじめに

AtCoder：競技プログラミングコンテストを開催する国内最大のサイト をはじめとする競技プログラミングでは、「割ったあまり」を求める問題が頻繁に出題されます。
そこで、Perl 用のテンプレートを準備します。

剰余の基本

割る整数を法といいますが、ここでは 1,000,000,007 を法として説明いたします。
変数の初期化は、お好きな方法で。

mod.pl

$mod1 = 1000000007;
$mod2 = 1_000_000_007;
$mod3 = 1e9 + 7;

print $mod1, "\n"; # => 1000000007
print $mod2, "\n"; # => 1000000007
print $mod3, "\n"; # => 1000000007

• 足し算

add.pl

$a += $mod + $b;
$a %= $mod;

変数が負のケースに対応するよう法を足しておきます。

• 引き算

sub.pl

$a += $mod - $b;
$a %= $mod;

マイナスにならない様、法を足しておきます。

• 掛け算

mul.pl

$a *= $b;
$a %= $mod;

• 割り算

割り算だけ別の計算が必要になります。

割り算の剰余：逆元

割り算の場合、法($mod)で直接割って求めることはできないので、法から逆元を求め、逆元を掛けることにより割り算の代用とします。

modinv.pl

sub modpow {
  my ($a, $n, $mod) = @_;
  my $res = 1;
  while ($n > 0) {
    $res = $res * $a % $mod if $n & 1;
    $a = $a * $a % $mod;
    $n >>= 1;
  }
  return $res;
}
sub modinv {
  my ($a, $mod) = @_;
  return modpow ($a, $mod - 2, $mod);
}
sub main {
  for (my $i=1; $i<13; $i++) {
    print "$i 's inv: " . modinv ($i, 13) . "\n";
  }
  my $a = 12345678900000;
  my $b = 100000;
  my $mod = 1_000_000_007;
  $a %= $mod;
  print $a * modinv ($b, $mod) % $mod, "\n"; # => 123456789
}
main();

$a に $b と $mod から求めた逆元を掛けて、$mod で余りを求めます。

print.pl

  print $a * modinv ($b, $mod) % $mod, "\n"; # => 123456789

ABC 156 D

AtCoder Beginner Contest 156 D - Bouquet

ABC156D.pl

use strict;
use warnings;

my ($n, $a, $b);
{
  my $in = <STDIN>;
  ($n, $a, $b) = split(" ", $in);
}
my $MOD = 1e9 + 7;
my $modpow = sub {
  my ($a, $n, $MOD) = @_;
  my $res = 1;
  while ($n > 0) {
    $res = $res * $a % $MOD if $n & 1;
    $a = $a * $a % $MOD;
    $n >>= 1;
  }
  return $res;
};
my $modinv = sub {
  my ($a, $MOD) = @_;
  return $modpow->($a, $MOD - 2, $MOD);
};
my $comb = sub {
  my ($n, $k) = @_;
  my $a = 1;
  my $b = 1;
  for (my $i=0; $i<$k; $i++) {
    $a *= $n - $i;
    $a %= $MOD;
    $b *= $i + 1;
    $b %= $MOD;
  }
  $a * $modinv->($b, $MOD) % $MOD;
};

my $ans = $modpow->(2, $n, $MOD) - 1;
$ans += $MOD - $comb->($n, $a, $MOD);
$ans += $MOD - $comb->($n, $b, $MOD);
print $ans % $MOD, "\n";

うーん、$MODだらけ

java の場合

javaの場合、java.math.BigInteger がライブラリとして準備されており、

• modInverse(BigInteger m)：逆元
• modPow(BigInteger exponent, BigInteger m)：べき乗
• gcd(BigInteger val)：最大公約数

などがメソッドとして利用可能です。

まとめ

• 本番で実装するには時間が短すぎる
• 習うより慣れよ

参照したサイト
「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜
クラスBigInteger
本日の精進：逆元と組み合わせ問題

追記

Perl で学ぶ逆元の２ + パナソニックプログラミングコンテスト2020 C で嵌った話 にて、AtCoder Beginner Contest 156 D - Bouquet の別解法を投稿しました。

追記２

足し算でも変数が負の場合、正しく計算されるように変更しました。
Perl で学ぶ逆元の３ ABC 151 E が解けた！