Miller-Rabin 素数判定と Pollard-Rho 素因数分解
Miller-Rabin 素数判定
Miller-Rabin 法は、フェルマーの小定理と二次探査定理を組み合わせた確率的素数判定アルゴリズムです。以下の手順で動作します。
偶数および 0, 1, 2 は事前に判定します。
判定対象の奇数 n に対し、n - 1 = 2s × d（d は奇数）と分解します。
小さな素数 a を基底として選び、ad mod n を計算し、その後 s 回の平方と二次探査を行います。
最 ...
5月28日 04:02 投稿
アルゴリズム実装と最適化テクニック
問題B：完全立方数を避ける数列選択
数列 $\{a_n\}$ から部分集合を選び、任意の2要素の積が完全立方数とならないようにする。$n\le 10^5$、$1\le a_i\le 10^{10}$。
重要な観察：$10^5$ より大きい素因数を持つ数は常に解答に寄与する。その他の数については、非1の完全立方因子をすべて除去してから処理する。
ll factorizeRandom(ll val) {
if (val % 2 == 0) re ...
5月19日 12:29 投稿