[過去ﾛｸﾞ]
プログラミングのお題スレ Part13 (1002ﾚｽ)
プログラミングのお題スレ Part13 http://mevius.5ch.net/test/read.cgi/tech/1549160513/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
632: デフォルトの名無しさん [sage] 2019/03/12(火) 19:26:28.38 ID:mUEXbKn8 お題 数列a[i]を考える。 a[0] = p a[i+1] = q * a[i] + r [入力] p q r n (p,q,r,nは整数) (0≦p,q,r≦99) (0≦n≦10^10) [出力] a[n] mod 13 を求めよ 1 2 0 8 => 9 (2^8 mod 13) 1 0 99 0 => 1 1 2 3 2 => 0 (a[0]=1, a[1]=2*1+3=5, a[2]=2*5+3=13) 1 3 5 10000000000 => ? http://mevius.5ch.net/test/read.cgi/tech/1549160513/632
635: デフォルトの名無しさん [] 2019/03/12(火) 21:07:56.58 ID:KPetEW8/ >>632 マシンパワーがあれば式を入れればいいだけってのはね。。。 解くのに頭使う。解いてみたら案外簡単(アルゴリズムが浮かぶのがキモ)。あえて難しくて最適化の道がある。とかが望ましい。 いあ、無茶振りだろうから、どれか2つ満たせればおkだが。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/635
640: デフォルトの名無しさん [sage] 2019/03/12(火) 23:07:31.93 ID:+VdOvnK/ >>632 https://ideone.com/Y4N5oM c++ 小さい数値は力技(bf2)で確認してみたが…… http://mevius.5ch.net/test/read.cgi/tech/1549160513/640
642: デフォルトの名無しさん [] 2019/03/12(火) 23:42:34.93 ID:2FAQzMGK >>632 C https://ideone.com/m3vejt エクセルとかで実際に数列を計算してみると、長さ12(剰余の数-1)以下の周期になるっぽいのでそれで求められる。 普通に計算するとq * a[i] + r はどんどん大きくなるけど、 毎回 (q * a[i] + r) mod 13としても、計算に影響はないようなので、オーバーフローもせずに計算できる。 だたし、数学的に正しいか保証しかねるが。 http://mevius.5ch.net/test/read.cgi/tech/1549160513/642
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.039s