数列における剰余の周期性
はじめに
競プロで剰余を利用する問題というと、1000000007で割ったあまりを出力せよ、みたいな問題とか、現在からn時間後の時刻を24時間表記で表せ、みたいな問題が思い浮かびますが、今回はそういったものではなく、数列における剰余の周期性についてです。
さも剰余の周期性についてある程度は理解しているような書き出しですが、センター試験以降は全くといっていいほど数学に触れてこなかった生粋の文学徒ですので、理解は大変浅いです。今後も間違った知識や考え方をひりだしていく可能性が非常に高いですが、ご指摘いただけるならそれ以上に嬉しいことはありません。では本題に移ります。
剰余の周期性
剰余の周期性について考えるきっかけになったのは以下の問題です。
B問題ですが、しばらく考えても全く理解できませんでした。そこで解説を見ると、
次に、A%B, 2A%B, 3A%B, ... という数列を考えます。なお A%B は A を B で割ったあまりを表します。
ここで、(k + B)A%B = (kA + BA)%B = kA%B に注目すると、この数列は周期的で、最初の B 個の要素を繰り返す数列になっていることがわかります。
この解説を見てますますわけがわからなくなりました。とくに「(k + B)A%B = (kA + BA)%B = kA%B」の数式が何をやっているのかまったくわかりません。しかし、余りに周期性があるという部分はなんとなく理解できます。
例えば「1から始まる奇数の数列」の「5で割ったあまり」を考えてみると、
1,3,5,7,9,11,13,15,17,19......
この数列の項をそれぞれ5で割ったあまりは
1,3,0,2,4,1,3,0,2,4......
となり、周期性が現れます。この場合、周期は5です。
1,2,3,4,5......の自然数の数列ではもちろんですが、どうやら今回の問題にあるような等差数列（そういえば倍数は等差数列ですね、いま知りました）でも、剰余に周期性が現れるようです。
さらに以下のサイトでは、同様に等比数列でも剰余に周期性が現れることが証明されています。
これらの数列における周期は、除数と等しくなっています。しかし以下のサイトによれば、特殊な数列（？）であるフィボナッチ数列では周期と除数が一致しないようです。
下の表を見ればわかるとおり、剰余の周期それ自体に、これまた周期性があるみたいですね。
問題を解く
では、これまでに得た知識を使って、先ほどの問題を解いてみます。問題を要約すると、
総和をBで割ったあまりがCとなるように、Aの倍数を1つ以上選ぶことができるか？
となります。
まず選ぶ個数ですが、解説にもあるように一つだけでよいです。
次に「Bで割ったあまりがCとなるようなAの倍数」を探します。前述したように、等差数列においては剰余に周期性がみられ、またその周期は除数と等しいので、「A,2A,3A,4A......BA」の幅Bの範囲のみ調べればよいことになります。
「A,2A,3A,4A......BA」のそれぞれについて実際にBで除算し、そのあまりがCとなっているかどうかを判定し、1つでもCになっていればその数を出力して終了です。
//abc060-b import java.util.*; class Main { static Scanner sc = new Scanner(System.in); static int mod = 1000000007; public static void main(String[] args) { int a = sc.nextInt(); int b = sc.nextInt(); int c = sc.nextInt(); for (int i=1; i<=b; i++) { if (a*i%b == c) { System.out.println("YES"); return; } } System.out.println("NO"); } }
