プログラミングのお題スレ Part22

296 ：デフォルトの名無しさん：2024/02/28(水) 23:21:09.16 ID:FCtvUtiC.net

>>284
>>294とは別の方法で>>292を高速化
https://ideone.com/QxjmyT

1³, 2³, 3³, …, 5000³をD = 5001で割った余りはすべて異なる値になるから、d = a³ − b³を
Dで割った余りはどれか1つの値に偏ることなく均等に分布する。dをDで割った余りによりdを
区分すれば、各区分に入る個数はどれも多すぎないのでソートに時間が余りかからない。
Dの値はconstexpr関数によりコンパイラに計算させている。n = 10000, 15000のときは
それぞれD = 10002, 15009になる。