【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\),判断一下即可。

最后去重一下

Subscribe
提醒
3 评论
最旧
最新 得票最多
Inline Feedbacks
View all comments
LCF
3 年 之前

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

LCF
3 年 之前
Reply to  LCF

所以就是O(跑得过)?