プチコン 非公式コミュニティ
トピック
こういち
◆.Id/aHiU36hu
2020/9/16 7:42
2020/9/16 7:42
コンテスト
問題(Lucas Number)
整数Nが与えられるので、N番目のリュカ数を20123で割ったあまりを求めなさい。
ただし、リュカ数とは以下の式で表される数です。
L(N+1)=L(N)+L(N-1)
L(N)=L(N)
L(0)=2
L(1)=1
ただし、リュカ数とは以下の式で表される数です。
L(N+1)=L(N)+L(N-1)
L(N)=L(N)
L(0)=2
L(1)=1
コメント
こういち
2020/9/16 7:43
◆.Id/aHiU36hu
入力は以下のように与えられます。
N
制約
0<=N<=2147483647
なお、事前知識が無いと難しいと思われるので、今回はヒントが与えられます。
N
制約
0<=N<=2147483647
なお、事前知識が無いと難しいと思われるので、今回はヒントが与えられます。
こういち
2020/9/16 7:44 ネタバレ
◆.Id/aHiU36hu
こういち
2020/9/16 7:45 ネタバレ
◆.Id/aHiU36hu
SatoshiMcCloud
2020/9/16 18:44
◆Z1qfV11i63Jr
L(N)=L(N)
↑はどういう意図…？
↑はどういう意図…？
こういち
2020/9/16 20:19 ネタバレ
◆.Id/aHiU36hu
Na
2020/9/16 23:06 ネタバレ
◆QoELVrBXBQCI
Na
2020/9/16 23:37 ネタバレ
◆QoELVrBXBQCI
さすらいの名無し
2020/9/17 8:52 ネタバレ
◆LWMA5UzCJb3e
こういち
2020/9/17 9:23 ネタバレ
◆.Id/aHiU36hu
SatoshiMcCloud
2020/9/17 12:19
◆Z1qfV11i63Jr
<証明>
割る数20123をMと置き換え、
F(N)=L(N) mod M
とする。
(i)定数Tに対し、
F(N)=F(N+T)
F(N-1)=F(N-1+T)
が成り立つ場合、
(A op B) mod C=((A mod C)op B)mod C
の性質から、
F(N+1)=L(N+1) mod M
=(L(N)+L(N-1)) mod M
=((L(N) mod M)+L(N-1))mod M
=(F(N)+L(N-1))mod M
=(F(N)+(L(N-1) mod M)) mod M
=(F(N)+F(N-1))mod M
=(F(N+T)+F(N-1+T)) mod M
=F(N+1+T)
(ii) F(N)=L(N) mod M
から、F(N)の値はMパターンしかない。
F(N)とF(N-1)の値が取りうる値の組み合わせは最大M^2であることから、0<=N<=M^2の範囲で必ず1回以上は F(N)=F(N+T) かつ F(N-1)=F(N-1+T) の組み合わせが出現することになる。
(iii)以上により、L(N)÷Mの余りは必ず周期性を持つ。周期TはT<=M^2である。
割る数20123をMと置き換え、
F(N)=L(N) mod M
とする。
(i)定数Tに対し、
F(N)=F(N+T)
F(N-1)=F(N-1+T)
が成り立つ場合、
(A op B) mod C=((A mod C)op B)mod C
の性質から、
F(N+1)=L(N+1) mod M
=(L(N)+L(N-1)) mod M
=((L(N) mod M)+L(N-1))mod M
=(F(N)+L(N-1))mod M
=(F(N)+(L(N-1) mod M)) mod M
=(F(N)+F(N-1))mod M
=(F(N+T)+F(N-1+T)) mod M
=F(N+1+T)
(ii) F(N)=L(N) mod M
から、F(N)の値はMパターンしかない。
F(N)とF(N-1)の値が取りうる値の組み合わせは最大M^2であることから、0<=N<=M^2の範囲で必ず1回以上は F(N)=F(N+T) かつ F(N-1)=F(N-1+T) の組み合わせが出現することになる。
(iii)以上により、L(N)÷Mの余りは必ず周期性を持つ。周期TはT<=M^2である。
SatoshiMcCloud
2020/9/17 23:22
◆Z1qfV11i63Jr
でも試してみると、M^2に対して周期Tがかなり小さい数値であることが多いのは、未だに解明できず…。
（既に出ている例でも、M=20123に対してT=40248だし）
（既に出ている例でも、M=20123に対してT=40248だし）
SatoshiMcCloud
2020/9/18 18:08
◆Z1qfV11i63Jr
さらに色々調べてみました。
(i)フィボナッチ数をF(n)とすると（先の証明のFとは無関係です）、フィボナッチ数とリュカ数の間には
L(n)=F(n-1)+F(n+1)
という関係が成り立つそうです。
(ii)フィボナッチ数をpで割った余りは、pを素数かつ5でも2でもないとして、
・pを5で割った余りが1または4なら、周期はp-1の約数
・pを5で割った余りが2または3なら、周期は2(p+1)の約数
という性質があるようです。
(iii)ここから、リュカ数をpで割った数はフィボナッチ数をpで割った数の周期と一致するかも、という予想が立てられます。
今回のケースはp=20123で、pを5で割った余りは3。周期は2(20123+1)=40248の約数と導けます。
おお、すごい、報告にあった周期とピタリ一致した！！！
(i)フィボナッチ数をF(n)とすると（先の証明のFとは無関係です）、フィボナッチ数とリュカ数の間には
L(n)=F(n-1)+F(n+1)
という関係が成り立つそうです。
(ii)フィボナッチ数をpで割った余りは、pを素数かつ5でも2でもないとして、
・pを5で割った余りが1または4なら、周期はp-1の約数
・pを5で割った余りが2または3なら、周期は2(p+1)の約数
という性質があるようです。
(iii)ここから、リュカ数をpで割った数はフィボナッチ数をpで割った数の周期と一致するかも、という予想が立てられます。
今回のケースはp=20123で、pを5で割った余りは3。周期は2(20123+1)=40248の約数と導けます。
おお、すごい、報告にあった周期とピタリ一致した！！！
こういち
2020/9/18 20:22
◆.Id/aHiU36hu
SatoshiMcCloudさん
さすがは貴金属数…まだまだ知らないことがありそうだ…
ちなみに、フィボナッチ素数が無限に存在するかどうかは未解決問題だそうです。
さすがは貴金属数…まだまだ知らないことがありそうだ…
ちなみに、フィボナッチ素数が無限に存在するかどうかは未解決問題だそうです。
こういち
2020/9/25 6:07
◆.Id/aHiU36hu
こういち
2020/9/25 6:24 ネタバレ
◆.Id/aHiU36hu
こういち
2020/9/25 20:33
◆.Id/aHiU36hu
一応、現実的でない解法も解説しておく。
現実的でない解法1 メモ化再帰
定義通りに再帰を組むことで求めることが出来ます。
DEF L(N)
IF N==0 THEN RETURN 2
IF N==1 THEN RETURN 1
RETURN (L(N-1)+L(N-2)) MOD 20123
END
ただし、制約が非常に大きいため、この方法だと計算が終わる頃には地球が滅亡しててもおかしくないです。(恐らくその前にStack overflowが出ますが)
そのため、一度計算した値を配列に入れておくことで、同じ計算をせずに済み一時間かからずに計算することが出来ます。
このように、一度計算した値を記録して再帰を回すテクニックをメモ化再帰と呼びます。
計算量はO(N)です。
嘘解法2
受けとるDP
FORで2番目のリュカ数から順に計算することで、O(N)で計算できます。このとき、計算に使うのは2つ前までの値だけなので、変数は2つと一時変数があれば十分です。
A=2,B=1,TMP
FOR I=0 TO N
TMP=B
B=(A+B) MOD 20123
A=TMP
NEXT I
PRINT A
嘘解法3 末尾再帰
再帰の仕方を工夫することで、メモ化を使わずにDPと同じ計算量を実現できます。(相変わらずStack Overflowはする)
現実的でない解法1 メモ化再帰
定義通りに再帰を組むことで求めることが出来ます。
DEF L(N)
IF N==0 THEN RETURN 2
IF N==1 THEN RETURN 1
RETURN (L(N-1)+L(N-2)) MOD 20123
END
ただし、制約が非常に大きいため、この方法だと計算が終わる頃には地球が滅亡しててもおかしくないです。(恐らくその前にStack overflowが出ますが)
そのため、一度計算した値を配列に入れておくことで、同じ計算をせずに済み一時間かからずに計算することが出来ます。
このように、一度計算した値を記録して再帰を回すテクニックをメモ化再帰と呼びます。
計算量はO(N)です。
嘘解法2
受けとるDP
FORで2番目のリュカ数から順に計算することで、O(N)で計算できます。このとき、計算に使うのは2つ前までの値だけなので、変数は2つと一時変数があれば十分です。
A=2,B=1,TMP
FOR I=0 TO N
TMP=B
B=(A+B) MOD 20123
A=TMP
NEXT I
PRINT A
嘘解法3 末尾再帰
再帰の仕方を工夫することで、メモ化を使わずにDPと同じ計算量を実現できます。(相変わらずStack Overflowはする)
こういち
2022/4/13 12:57 ネタバレ
◆.Id/aHiU36hu
コメントを書く
- こちらは「プチコン3号」「プチコンBIG」など、プチコンシリーズに関する話題を扱ったコミュニティです
- プチコンシリーズにまったく関係ない書き込みはご遠慮下さい。削除の対象となります
- こちらにはその他のゲームや雑談のコミュニティはなく、作る予定もありません (ひとりで管理できないため)。ごめんなさい
- ユーザー登録なしで書き込みができます
- 秘密の合い言葉は成りすましの防止 (トリップ機能)、書き込みの編集時の本人認証に使用します
- 秘密の合い言葉に他人に推測されやすい言葉、他サービスと同じパスワードは入力しないでください。
- 書き込むと、投稿時に入力したお名前と秘密の暗号が記憶され、ログイン状態になります