BZOJ 1406 密码箱

http://www.lydsy.com/JudgeOnline/problem.php?id=1406

题意:给定n，求x^2==1%n

x^2-1=k*n

(x+1)*(x-1)==k*n

(x+1)(x-1)%n=0

n=a*b

则有(x+1)|a且(x-1)|b 或 (x-1)|a且(x+1)|b

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<string>
 6 #include<algorithm>
 7 #include<set>
 8 #define ll long long
 9 using namespace std;
10 int n;
11 set<int> ans;
12 int main(){
13     scanf("%d",&n);
14     int len=(int)sqrt(n);
15     ans.insert(1);
16     for (int i=1;i<=len;i++)
17      if (n%i==0){
18         int a=n/i,b=i,x;
19          for (x=a+1;x<=n;x+=a)
20           if ((x+1)%b==0) ans.insert(x);
21          for (x=a-1;x<=n;x+=a)
22          if ((x-1)%b==0) ans.insert(x);
23      }
24     for (set<int>::iterator i=ans.begin();i!=ans.end();i++) printf("%d
",*i);
25 }