平方数判定をする際にいくらか高速化できるテクニックを知ったのでメモしておく。 nが偶数の平方の場合は、 n = 2k * 2k = 4k^2 と表すことが出来る。よって4で割った余りは0。 nが奇数の平方の場合は、 n = (2k + 1) * (2k + 1) = 4k^2 + 4k + 1 と表すことが出来る。よって4で割った余りは1。 ということで、3とビットのandを取って1より大きくなった場合、その 数は平方数ではないことが分かる。
平方数を4で割った余り
平方数判定をする際にいくらか高速化できるテクニックを知ったのでメモしておく。 nが偶数の平方の場合は、 n = 2k * 2k = 4k^2 と表すことが出来る。よって4で割った余りは0。 nが奇数の平方の場合は、 n = (2k + 1) * (2k + 1) = 4k^2 + 4k + 1 と表すことが出来る。よって4で割った余りは1。 ということで、3とビットのandを取って1より大きくなった場合、その 数は平方数ではないことが分かる。
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
