BZOJ 1406 [AHOI2007] 密码箱

发布于 2017-04-28  161 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1406

题意:给出一个 n,求所有满足 0≤x<n 且 x2%n=1 的整数 x...


大水题 qwq....... 首先我们有\(x^{2}=kn+1\)... 然后移项,因式分解后有\((x+1)(x-1)=kn\)...

我们令\(x+1=k_1n_1\)  \(x-1=k_2n_2\)... 枚举 n 的因数 (\(O(\sqrt {n})\)) 即可得到 n1,n2,然后枚举一项 k 检验另一项是否合法即可...

但是直接这样搞答案会有重复... 我们需要处理一下判重... 蒟蒻并不会 set... 只能乱搞一下了....

另外 bzoj 数据水的不行... 不开 long long 也能过... 代码如下:

 


一个非常弱的准退役OIER