モジュール演算 (Modular arithmetic)
私たちは多くの場合、計算結果そのものの絶対値ではなく、
m で割ったときの余り、すなわち「計算結果を m で割った剰余」に焦点を当てることがあります。おもしろいことに、私たちは日常的にモジュール演算を扱っています。たとえば時計を見るとき、その年の始めから何時間経過しているかという絶対的な時間ではなく、「今の時刻」という観点に注目します。これは、12 時制であれば時間を 12 で割った余り、24 時制であれば 24 で割った余りを見ているのと同じことです。時刻が進むにつれ、時計の表示は 0 時から 1 時、2 時、3 時…と 11 時に至ったら再び 0 時に戻り、このサイクルが延々と続いていきます。表示される値は常に 0 から 11 の範囲内で、年初からの経過時間を
h としたとき、「現在の時刻」は h % 12 で求めることができます。
たとえば「ある数の下1桁」に着目する場合、これは 0、1、2、…、9 までの 10 個の目盛りをもつ「10 時制の時計」を見ているようなものです。数値に 1 を足すたびに、下1桁は 9 に至るまでインクリメントされますが、9 の次にもう 1 を足すと 0 に戻ります。任意の数
n に対して、その下1桁は n % 10（n を 10 で割った余り）で求めることができます。次に、ビット（0 と 1）の場合を考えてみましょう。これは 0 と 1 の 2 つしか目盛りがない「2 時制の時計」のようなものです。0 に 1 を足すと 1 になり、1 に 1 を足すと 0 に戻ります。任意のビット列を表す数
n について、その最下位ビットは n % 2（n を 2 で割った余り）でわかります。このように、モジュール演算とは「
m 個の目盛りをもつ時計」を扱うのと同じです。時刻の例では m が 12、下1桁の例では m が 10、ビットの例では m が 2 になっています。実際には、それぞれの問題設定に応じて m を自由に選ぶことができ、たとえば大きな素数 10^9 + 7 などを使うこともあります。これは計算を簡単にすませず、正しく処理するために選ばれることが多い数値です。加算 (Addition) のモジュール演算
2 つの数
a と b の加算について、私たちが興味を持つのが結果の m での剰余だけである場合、たとえば「下1桁だけ」に注目したいなら、その結果は m が 10 のときの剰余です。さらに計算をシンプルにするためには、まず a の m での剰余と b の m での剰余をそれぞれ求め、それを足し合わせてから再度 m で割った剰余を取ります。たとえば res = (a % m + b % m) % m のように書けます。減算 (Subtraction) のモジュール演算
a から b を引く操作をモジュール演算で考えると、たとえば時計の針を a の状態から b 時間分戻すイメージになります。(5 - 2) % 12 = 3 のように、5 時から 2 時間戻すと 3 時になりますし、(5 - 7) % 12 = -2 % 12 = 10 のように、5 時から 7 時間戻す場合はいったん -2 になってから 10 に置き換えています。さらに、m よりも大きい数を扱うときには、まずそれぞれ m の剰余を取ってから引けばよいので、たとえば (21 % 10 - 18 % 10) % 10 = (1 - 8) % 10 = 3 のようになります。言語によっては（Python のように）
% 演算子が常に正の値を返す実装になっている場合もありますが、C++ のように負の値を返す可能性がある言語も存在します。負の値が出る言語で扱う場合には、時計を 1 周先へ進めるイメージで（-2 に対して 12 を加えて 10 にするなど）最終的に正の値に調整します。乗算 (Multiplication) のモジュール演算
2 つの数を掛け算するときも、結果は
m で割った剰余で求めることができます。たとえば m が 10 の場合、掛け算した結果の下1桁を知りたいときに同様の考え方が使えます。除算 (Division) のモジュール演算
除算は、ここまでの演算よりも少し厄介です。たとえば下1桁だけで考える場合、「28 ÷ 7 = 4」のため結果の下1桁は 4 ですが、28 の下1桁（8）と 7 の下1桁（7）を使って単純に計算しても 4 は出てきません。モジュール演算での除算を行うにはオイラーの定理などを使うことができ、詳しくは以下のリンクで解説されています。
チャレンジ: m を法としたべき乗計算
入力として与えられる
x, n, m を使って、 の値を求める問題です。入力
x, n (1 ≤ n ≤ 10^6), および m (1 ≤ x, m ≤ ) の 3 つの整数が与えられます。
出力
の結果を出力してください。
例
入力 | 出力 |
2 6 10 | 4 |
3 2 4 | 1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB