数列の剰余の周期性がわからない

はじめに

• $\color{green}{具体的な証明、誰にでも分かる解説はこちらではありません。}$他をあたってください

これはABC179-Eで余りの周期性を使う問題があったので自らの理解のために書いたものです。正確性に関して、努力はしますが必ずしも正確とは言い切れません。また、私は数ⅠA,Ⅱのある程度の知識を持っているので、そこから理解しようとしています

鳩ノ巣原理ってなんだよ

コンテスト後のTwitterのTLを見ていると、鳩ノ巣原理というのが飛び込んできました。 細かい説明はいろいろなサイトがやっているので省いて、簡単な説明をすると $ M $の区切りの中に$ N $個($ N > M $)のものを入れると、必ずどこかの区切りで重なる

というものらしい

今わかってること

今回の問題の概要は問題文から漸化式が出てくること

そんで、基本的に$ N > M $だと考えると、あまりの取りうる値が0,1,2,... M-2,,M-1だからどこかで余りがかぶるのは理解できた

んで、今理解できてないのはx ≡ y² mod Mのときにそれは周期性を持ってるのかというところ

本題

高校数学の美しい物語さんによると、(an,a{n+1}) と (a{n2} , a{n2+1})の組はたかだかM²しかないから鳩ノ巣原理から (an,a{n+1}) と (a{n2} , a{n2+1}) の組が等しいものが存在するということらしい。

今回の制約は N ≦ 10¹⁰ , M　≦ 10⁵ なので成り立ちそうではある

いままで、a{n1} ≡ a{n2} mod Mのことばかり考えていたけれども、組で考えると、自明な気がしてきた

まとめ

余りの問題で、 M² < N なら周期性が使えそうだということがわかった。

ところで、ダブリングだと何も考えずに解けるらしい(伝聞)のでこれも勉強してみたい