プログラミングのお題スレ Part22 (863ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
296(4): 2024/03/01(金)22:22 ID:6k2oCbjk(1/3) AAS
>>282
C++
外部ﾘﾝｸ:ideone.com
>>294はa, bの二重ループ内でa³ − b³をD = 5001で割った余りrにより区分していたが、
rのループ内でa, bを変化させるように変更したら、2次元配列がなくなってすっきりした。
その結果、メモリ使用量が激減し、nが大きい場合でも実行できるようになった。
297(1): 2024/03/01(金)22:23 ID:6k2oCbjk(2/3) AAS
>>296の続き
n = 1000000, m = 6で実行すると、12通りの解が見つかった。
[6つ組解]
424910390480793: (75978, 23919), (77385, 33768), (83482, 53935), (141705, 134268), (317982, 316575), (596001, 595602)
620174235433536: (86184, 27132), (87780, 38304), (90237, 48573), (94696, 61180), (160740, 152304), (360696, 359100)
1238805803151000: (107487, 14487), (108540, 34170), (110550, 48240), (119260, 77050), (454260, 452250), (851430, 850860)
1384074844012224: (112152, 29844), (125324, 83600), (130050, 93426), (159372, 138624), (224928, 215412), (357447, 353799)
省11
298(1): 2024/03/01(金)22:24 ID:6k2oCbjk(3/3) AAS
>>282
C++
外部ﾘﾝｸ:ideone.com
>>296のrのループ内でa³ − b³をD2 = 5003で割った余りr2により区分し、それぞれの区分ごとに
解を探すようにしたら速くなった。ただし、nが大きい場合にはかえって遅くなる。
300(1): 2024/03/03(日)22:19 ID:ZEDvt9uH(1) AAS
>>282
C++
外部ﾘﾝｸ:ideone.com
>>298でnを大きくするにつれ>>296に対する高速化効果が薄れていくのは、ABをvectorでなく
配列にしたらある程度改善された。n = 5000のときの実行時間は>>296の半分以下になった。
ただし、n = 1000000まで大きくすると、296よりやっぱり遅くなる。
>>299
省1
301(3): 2024/03/06(水)22:35 ID:lIZep5aT(1) AAS
>>282
C++
外部ﾘﾝｸ:ideone.com
>>300の実行時間を分析すると、最も時間が掛かっているのは46〜と47行目だと判明した。
そこで配列ABの第1次元と第2次元を入れ替えてみると、n = 5000では変わらないが、
1万, 2万, 5万, 10万, 20万では35%前後高速になった。これは、改良前には第2次元の添字が
小さい要素に書き込みが集中しているため、改良後のように第1次元に入れ替えた方が
省8
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.028s