Problem 124 - PukiWiki nの素因数の積をrad(n)とする．例えばrad(504) = 2*3*7 = 42である． ある範囲について求めたrad(n)を，rad(n)を第1キー，nを第2キーとしてソートする．このときソート結果のk番目にあるnの値をE(k)とする．例えば1≦n≦10についてrad(…

Problem 123 - PukiWiki Problem 120と同種の問題．n番目の素数をp_nとし，(p_n - 1)^n + (p_n + 1)^nをp_n^2で割った余りが10^10より大きくなる最初のnを求める． 27ms．素数の探索範囲は適当．

Problem 122 - PukiWiki さっぱり解ける気がしないので色々調べている過程でKnuthのpower tree methodというものの存在を知った．それでどうにか理解したものの残念なことにこの問題を単純なpower treeで解くことはできない． 結局Evaluation of Powers | CO…

指数の計算 a^nを素朴に計算するとn-1回の乗算が必要になる．例えばa^5なら a^2 = a * a a^3 = a^2 * a a^4 = a^3 * a a^5 = a^4 * a しかし，少し工夫することによって乗算の回数は節約できる．例えばa^15は5回の乗算で計算できる． a^2 = a * a a^4 = a^2 …