http://www.lydsy.com/JudgeOnline/problem.php?id=1406
| Description 在一次偶然的情况下，小可可得到了一个密码箱，听说里面藏着一份古代流传下来的藏宝图，只要能破解密码就能打开箱子，而箱子背面刻着的古代图标，就是对密码的提示。经过艰苦的破译，小可可发现，这些图标表示一个数以及这个数与密码的关系。假设这个数是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 |
显然O(N)是不行的。我们有：
x^2≡1(mod n)
x^2=kn+1
x^2-1=kn
(x-1)(x+1)=kn
因为(x-1)(x+1)|n,则(x-1)(x+1)的约数一定是n的约数。我们可以先分解出n的约数t[i]，再枚举j,使t[i]*j=x-1或x+1，再计算出(x+1)=t[i]*j+2或(x-1)=t[i]*j-2，验证是否符合(x-1)(x+1)|n，若符合，判重后加入答案表。最后排序后输出即可。
有几个容易写挫的地方：1、几个变量要用int64 2、数组不要开小 3、计算(x-1)(x+1)时先分别对n取mod后乘，否则会溢出，此对判别乘积的mod无任何影响。
program p1406;
Var
i,j,ct,top:longint;
t,ans:array[0..60000] of int64;
y,n:int64;
procedure fopen;
begin
assign(input,'p1406.in');
assign(output,'p1406.out');
reset(input);
rewrite(output);
end;
Procedure fclose;
begin
close(input);
close(output);
end;
Function inset(P:int64):boolean;
var
i:longint;
begin
for i:=1 to top do
if ans[i]=p then exit(true);
exit(false);
end;
Procedure insert(P:int64);
begin
inc(top);
ans[top]:=p;
end;
begin
fopen;
readln(n);ct:=0;
fillchar(ans,sizeof(ans),0);
fillchar(t,sizeof(t),0);
for i:=1 to trunc(sqrt(n)) do
if (n) mod i=0 then
begin
inc(ct);
t[ct]:=i;
if i*i<>n then
begin
inc(ct);
t[ct]:=n div int64(i);
end;
end;
top:=0;
if n>1 then insert(1);
for i:=1 to ct do
if t[i]<n-1 then
for j:=1 to round(sqrt(n))+10 div t[i] do
if ((t[i]*j mod n)*((t[i]*j+2) mod n)) mod n=0 then
if t[i]*j+1<n then
if not inset(t[i]*j+1) then insert(t[i]*j+1);
for i:=1 to ct do
if t[i]>2 then
for j:=1 to round(sqrt(n))+10 div t[i] do
if ((t[i]*j mod n)*((t[i]*j-2) mod n)) mod n=0 then
if (t[i]*j-1<n) and (t[i]*j-1>0) then
if not inset(t[i]*j-1) then insert(t[i]*j-1);
for i:=1 to top do
for j:=i+1 to top do
if ans[i]>ans[j] then
begin
y:=ans[i];
ans[i]:=ans[j];
ans[j]:=y;
end;
if top=0 then writeln('None');
for i:=1 to top do
writeln(ans[i]);
fclose;
end.