[過去ﾛｸﾞ] プログラミングのお題スレ Part21 (1002ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
797(2): デフォルトの名無しさん [] 2023/06/16(金) 20:29:55.57 ID:2udbfubS(1/2) AAS
>>738738(13): デフォルトの名無しさん [] 2023/06/08(木) 22:14:54.10 ID:B/+C/EDE(2/2) AAS
お題：1234567以下の素数 a, b, c で a + b + c = 1234567 かつ a ≤ b ≤ c を満たす組み合わせは何通りあるか計算せよ。
外部ﾘﾝｸ:paiza.io
細かいテクニックで高速化して出題者の方の解答例と同じくらいの実行時間にできた
総当たりの解法の計算量が N = 1234567 に対して O(pi(N)^2) なのに対してこの解法は O(N log N) なのできちんと書けば十分に速く動いてくれる
803: デフォルトの名無しさん [] 2023/06/16(金) 22:11:45.10 ID:2udbfubS(2/2) AAS
>>798大体わかっているみたいだけど少し丁寧に書いてみる
素数次数の係数が 1 でそれ以外の係数が 0 の形式的冪級数 f を考える
f^3 の k 次の項の係数は 素数 3 個を選んで足した和が k になる場合の数になるので今回は k = 1234567 の係数を求めたい
長さ N の多項式の積は高速フーリエ変換による畳み込みで O(N log N) で計算できるので形式的冪級数を前から必要なだけとって多項式にして適用する
また取りうる値が大きくて誤差が問題になるときは数論変換と中国剰余定理で復元する方法もあるけど今回は不要
3乗している対象は配列の各項なのでそこはボトルネックにはならない
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.037s