数論・組み合わせ・対頂ヒープを用いた競技プログラミング問題の解析と実装
問題A：平方倍数の探索
問題概要
正の整数 k が与えられる。k | n^2 （n^2 は k の倍数）かつ n が k の倍数ではないという条件を満たす最小の正の整数 n を求める。
解法の考察
求める n^2 は k の倍数であるため、n^2 = m * k と表せる。ここで n は k の倍数ではないため、m は 1 以上 k-1 以下の範囲に存在する。m を直接全探索すると計算量が O(k) となりTLEする。
...
9月17日 20:44 投稿