【BZOJ1406】【AHOI2007】密码箱

$$x^2\equiv 1\bmod n$$
$$x^2-1=kn$$
$$(x+1)(x-1)=kn$$

令\(x+1=k_1n_1\),\(x-1=k_2n_2\)

那么假设\(n_1\)和\(n_2\)中必有一个不小于\(\sqrt{n}\),枚举其再枚举\(k_1n_1\),判断一下即可。

最后去重一下

说点什么

3 评论 在 "【BZOJ1406】【AHOI2007】密码箱"

提醒
排序:   最新 | 最旧 | 得票最多
成员

复杂度似乎是O(sqrt(n)*sqrt(n))=O(n)?

成员

所以就是O(跑得过)?

wpDiscuz