Search on the blog

2015年4月18日土曜日

平方数を4で割った余り


平方数判定をする際にいくらか高速化できるテクニックを知ったのでメモしておく。

nが偶数の平方の場合は、
n = 2k * 2k = 4k^2
と表すことが出来る。よって4で割った余りは0。

nが奇数の平方の場合は、
n = (2k + 1) * (2k + 1) = 4k^2 + 4k + 1
と表すことが出来る。よって4で割った余りは1。

ということで、3とビットのandを取って1より大きくなった場合、その 数は平方数ではないことが分かる。

0 件のコメント:

コメントを投稿