数论
Orz iwtwiioi
果然数论很捉鸡>_>完全不知道怎么下手
$$x^2 \equiv 1 \pmod n \rightarrow (x+1)*(x-1)=k*n $$
所以，我们得到$$n | (x+1)(x-1)$$
那么有什么用呢？注意到整除是个神奇的关系= =所以我们可以令$n=a*b$，那么对于每个x，一定有$a|(x+1) 且 b|(x-1)$ 或是 $a|(x-1) 且 b|(x+1)$
然后？我们可以$O(\sqrt{n})$枚举a，得到b，然而，x+1（或者x-1）是b的倍数！所以我们可以枚举这个倍数，再判断与它对应的x-1（或x+1）是否满足与a的整除关系，就可以找到x啦！
最后再用set判重……
Orzzzzzz……
太神了……
/**************************************************************
Problem: 1406
User: Tunix
Language: C++
Result: Accepted
Time:8 ms
Memory:1276 kb
****************************************************************/ //BZOJ 1406
#include<set>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
typedef long long LL;
set<LL> s;
set<LL>::iterator it;
int main(){
#ifndef ONLINE_JUDGE
freopen("1406.in","r",stdin);
freopen("1406.out","w",stdout);
#endif
LL n; scanf("%lld",&n);
for(LL i=;i*i<=n;i++) if (n%i==){
LL j=n/i,x;
for(LL k=;j*k+<n;k++){
x=j*k+;
if ((x+)%i==) s.insert(x);
}
for(LL k=;j*k-<n;k++){
x=j*k-;
if ((x-)%i==) s.insert(x);
}
}
if (!s.size()){puts("None");return ;}
for(it=s.begin();it!=s.end();it++)
printf("%lld\n",*it);
return ;
}
1406: [AHOI2007]密码箱
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 877 Solved: 509
[Submit][Status][Discuss]
Description
在一次偶然的情况下，小可可得到了一个密码箱，听说里面藏着一份古代流传下来的藏宝图，只要能破解密码就能打开箱子，而箱子背面刻着的古代图标，就是对密
码的提示。经过艰苦的破译，小可可发现，这些图标表示一个数以及这个数与密码的关系。假设这个数是n，密码为x，那么可以得到如下表述：
密码x大于等于0，且小于n，而x的平方除以n，得到的余数为1。
小可可知道满足上述条件的x可能不止一个，所以一定要把所有满足条件的x计算出来，密码肯定就在其中。计算的过程是很艰苦的，你能否编写一个程序来帮助小
可可呢？（题中ｘ，ｎ均为正整数）
码的提示。经过艰苦的破译，小可可发现，这些图标表示一个数以及这个数与密码的关系。假设这个数是n，密码为x，那么可以得到如下表述：
密码x大于等于0，且小于n，而x的平方除以n，得到的余数为1。
小可可知道满足上述条件的x可能不止一个，所以一定要把所有满足条件的x计算出来，密码肯定就在其中。计算的过程是很艰苦的，你能否编写一个程序来帮助小
可可呢？（题中ｘ，ｎ均为正整数）
Input
输入文件只有一行，且只有一个数字n(1<=n<=2,000,000,000)。
Output
你的程序需要找到所有满足前面所描述条件的x，如果不存在这样的x，你的程序只需输出一行“None”(引号不输出)，否则请按照从小到大的顺序输出这些x，每行一个数。
Sample Input
12
Sample Output
1
5
7
11
5
7
11