[文章目录]
Description
假设这个数是n，密码为x，那么可以得到如下表述： 密码x大于等于0，且小于n，而x的平方除以n，得到的余数为1。 小可可知道满足上述条件的x可能不止一个，所以一定要把所有满足条件的x计算出来，密码肯定就在其中。计算的过程是很艰苦的，你能否编写一个程序来帮助小可可呢？（题中ｘ，ｎ均为正整数）n<=2*10^9
简单变幻：
x^2=1(mod n)
x^2-1=k*n
(x-1)*(x+1)=k*n
假设n=A*B，那么一定有A|(x-1)&&B|(x+1)
由于x是在0~n之间，所以对于A、B中大于√n的那个只对应小于√n个x。
枚举大的约数的倍数，统计答案之后去重就好了。
时间复杂度O(n的约数中小于√n的约数的和)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll n,ans[1001000],tot;
int main()
{
scanf("%lld",&n);
ll i,j,k;
for(i=1;i*i<=n;++i) if(n%i==0)
{
k=n/i;
for(j=0;j<=n;j+=k)
{
if(j*(j+2)%n==0&&j+1<n) ans[++tot]=j+1;
if((j-2)*j%n==0&&j-1>0) ans[++tot]=j-1;
}
}
if(!tot){ puts("None"); return 0;}
sort(ans+1,ans+tot+1); ans[0]=-1;
for(i=1;i<=tot;++i) if(ans[i]!=ans[i-1])
printf("%lld\n",ans[i]);
return 0;
}