整数 A を M で割った余りと、整数 B を M で割った余りが等しい場合、「M を法として A と B は合同である」といい A ≡ B(mod M)と表されます。
mod の逆元
M と互いに素である整数 A に対して、 A × N ≡ 1(mod M) となる 1 以上 M 未満の整数が必ず存在し、これを「mod M での A の mod 逆元」といい、 A^{-1} (mod M) と書きます。
互いに素である整数 A , M が与えられるので、mod M での A の mod 逆元を求めてください。
ただし、答えは 1 以上 M 未満の整数で出力してください。入力されるデータ
M A
（ただし 2 ≦ M ≦ 100,000
2 ≦ A ≦ 100,000
M と A は互いに素 ）
逆元を求めたいときはどうすればよいのでしょうか？
x, y についての 1 次方程式 Ax + My = 1 の 解 x が A の 逆元です。gcd(A, M) = 1 であるので、この方程式の解 x は拡張ユークリッドの互除法を用いることで求めることができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
using System; using System.Collections.Generic; using System.Linq; public class Program { // gcd(a, b) と ax + by = gcd(a, b) の解 x , y を求める static long Extgcd(long a, long b, ref long x, ref long y) { long c = a; if (b != 0) { c = Extgcd(b, a % b, ref y, ref x); y -= (a / b) * x; } else { x = 1; y = 0; } return c; } static void Main() { int N, A; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; A = vs[1]; } //mod M での A の mod 逆元を求めるには、 x , y についての 1 次方程式 Ax + My = 1 の 解 x が分かれば良い long x = 0; long y = 0; Extgcd(A, N, ref x, ref y); if (x < 0) // 答えは 1 以上 M 未満の整数なので x += N; Console.WriteLine(x); } } |
mod の累乗
競技プログラミングの問題のなかには「答えの値は非常に大きな値になることがあるので 10^9 + 7 で割ったあまりを出力してください」と書かれているものがあります。mod の累乗の高速な計算をしたいときはどうすればよいのでしょうか？
整数 A , B , M が与えられるので、 A^B(mod M) を求めましょう。
A B M
（ただし、1 ≦ A, B, M ≦ 100,000）
最大 100,000 乗を考えなければならないのでループを回していては時間が足りません。実際には100,000回程度のループであれば間に合うのかもしれませんが、繰り返し二乗法を使えば累乗指数がもっと大きな数になっても対応できます。
まず b の 2 進数表現を考える。b の最下位の桁が 1 かどうかを確認する。
最下位の桁が 1 の場合、a を ans にかける。
そのあと、a を a の 2 乗に置き換え、b を右に 1 ビットシフトする(つまり 2 で割る)。
この方法ならmod の累乗を高速に計算することができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
using System; using System.Collections.Generic; using System.Linq; public class Program { // a の b乗（mod m）を返す static long modpow(long a, long b, long m) { long ans = 1; while (0 < b) { if ((b & 1) == 1) ans = (ans * a) % m; // A, B, M ≦ 100,000 であることから int だとオーバーフローしてしまうので注意！ a = (a * a) % m; b >>= 1; } return ans; } static void Main() { long A, B, M; { long[] vs = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); A = vs[0]; B = vs[1]; M = vs[2]; } Console.WriteLine(modpow(A, B, M)); } } |
mod の階乗
整数 n が与えられる。n! mod (10^9 + 7)を答えよ。
入力されるデータ
n
（ただし 0 ≦ n ≦ 10^18）
普通に階乗を計算しようとすると計算量はO(n)になります。そのため n ≦ 10^18 という条件があると間に合いません。
もし n が 10^9 + 7 以上の場合は n! は 10^9 + 7 の倍数となり、n! ≡ 0 mod (10^9 + 7)となります。では n が 10^9 + 7 未満で比較的大きな値の場合はどうやって計算量を減らせばよいでしょうか？
もし n = 900000006 の場合、n = 900000000 のときの n! mod (10^9 + 7) の値がわかっていればこの値を利用して処理を高速化することができます。
若干時間がかかりますが、事前に以下のようなコードを実行して答えを出力しておきます。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
static void func() { long mod = 1000000007; long a = 1; for (long i = 1; i < mod; i++) { a = a * i % mod; if (i % 50000000 == 0) Console.WriteLine(a); } } |
すると以下のような出力が得られました。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
67347853 927880474 // (1 * 10^8)! % mod 261384175 933245637 // (2 * 10^8)! % mod 112390913 668123525 // (3 * 10^8)! % mod 386027524 429277690 // (4 * 10^8)! % mod 462639908 733333339 // (5 * 10^8)! % mod 696628828 724464507 // (6 * 10^8)! % mod 92255682 957939114 // (7 * 10^8)! % mod 217598709 203191898 // (8 * 10^8)! % mod 823845496 586445753 // (9 * 10^8)! % mod 315103615 698611116 // (10 * 10^8)! % mod |
この値を利用して以下のようなコードを書きます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
using System; using System.Collections.Generic; using System.Linq; public class Program { static long ModFactorial(long n) { long mod = 1000000007; if (n == 0) return 1; // 0! == 1 なので // n が 10^9 + 7 以上なら n! mod (10^9 + 7)は 0 になる if (n >= mod) return 0; long[] catche_list = { 1, 67347853, 927880474, // (1 * 10^8)! % mod 261384175, 933245637, // (2 * 10^8)! % mod 112390913, 668123525, // (3 * 10^8)! % mod 386027524, 429277690, // (4 * 10^8)! % mod 462639908, 733333339, // (5 * 10^8)! % mod 696628828, 724464507, // (6 * 10^8)! % mod 92255682, 957939114, // (7 * 10^8)! % mod 217598709, 203191898, // (8 * 10^8)! % mod 823845496, 586445753, // (9 * 10^8)! % mod 315103615, 698611116, // (10 * 10^8)! % mod }; // n を 50000000で割った商が catche_list のインデックスになり起点が求まる long start = n / 50000000; long ans = catche_list[start]; //起点から階乗の計算を始める for (long i = start * 50000000 + 1; i <= n; i++) ans = ans * i % mod; return ans; } static void Main() { long n = long.Parse(Console.ReadLine()); Console.WriteLine(ModFactorial(n)); } } |
