BZOJ 1406 [AHOI2007] 密码箱


题目链接: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 也能过... 代码如下:

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 1406 [AHOI2007] 密码箱


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,