【bzoj1406】[AHOI2007]密码箱

x²≡ 1 mod n => x²= k * n + 1 => n | (x + 1) * (x - 1)

令n = a * b，则 (a | x + 1 且 b | x - 1) 或 (a| x - 1 且 b | x + 1)

于是暴力枚举a ∈ [1, sqrt(n)] 就好了

然后直接丢到set里判重

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 #include<queue>
 8 #include<set>
 9 using namespace std;
10  
11 typedef long long LL;
12  
13 LL n;
14  
15 set<LL>s;
16  
17 int main()
18 {
19     scanf("%lld",&n);
20     for (int i=1;i<=(int)sqrt(n);i++)
21         if (n%i==0)
22         {
23             LL x=n/i;
24             for (LL j=1;j<=n;j+=x)
25                 if ((j+1)%i==0)
26                     s.insert(j);
27             for (LL j=x-1;j<=n;j+=x)
28                 if ((j-1)%i==0)
29                     s.insert(j);
30         }
31     if (s.empty())
32     {  
33         printf("None
");
34         return 0;
35     }
36     while (!s.empty())
37     {
38         printf("%lld
",*s.begin());
39         s.erase(s.begin());
40     }
41     return 0;
42 }