【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
说点什么

1 Comment threads
2 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
成员
LCF

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

成员
LCF

所以就是O(跑得过)?