プログラミングのお題スレ Part22 (860ﾚｽ)
プログラミングのお題スレ Part22 http://mevius.5ch.net/test/read.cgi/tech/1691038333/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
ﾚｽ栞
ﾘﾛｰﾄﾞ規制
です｡10分ほどで解除するので､
他のﾌﾞﾗｳｻﾞ
へ避難してください｡
754: デフォルトの名無しさん [] 2025/04/12(土) 21:18:53.69 ID:RVQAocGC >>741のC++プログラムは for (int i = S; i >= 2; i--) のループの最後のi = 2の場合を ループの外に出して最適化 (p[S]以外のp[_]への要素追加をしないように) するだけで、 20億以下で解の出力なしのときの実行時間が元のプログラムの半分未満になるな。 https://ideone.com/RtTEO2 (1.02秒) ↓ https://ideone.com/1O04wl (0.44秒) http://mevius.5ch.net/test/read.cgi/tech/1691038333/754
755: デフォルトの名無しさん [sage] 2025/04/12(土) 21:26:41.27 ID:csJOBVaF >>754 それに気づいたけど まだ>>750と比べて20倍遅いからメモ化の方針が徒となってるのかな http://mevius.5ch.net/test/read.cgi/tech/1691038333/755
760: デフォルトの名無しさん [sage] 2025/04/17(木) 00:29:06.02 ID:dz0qzhSq >>741 2000万個すべてを素因数分解する方法とは逆に、 2025以下の素数の組み合わせを調べていく方法。 そのうち和が2025になる組み合わせの積が各解となる。 それを効率よく求めるために2025(+1)個のベクタのベクタpを用意している。 つまり和がsumとなる時の積をp[sum]に記録していく。 効率面からの仮の初期値p[0]に1を入れて、各素数iについて降順に、 ベクタp[j]にxがある時、ベクタp[i+j]にx*iをpushしていく。 ここでjの上限は 2025 - i、処理するxの上限は 2000万 / i の枝刈りができる。 最終的にベクタp[2025]の一覧が解となる。 2025個のベクタを用いることが長所および短所になっている。 この改良版>>754では、最後の素数2だけ特別扱いすることで倍速にしている。 http://mevius.5ch.net/test/read.cgi/tech/1691038333/760
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.033s