数学。
x^2 % n = 1 则 (x+1)(x-1) = kn.
设 x+1 = k1*n1, x-1=k2*n2。 则 k1*k2=k , n1*n2=n。
算出每个大于sqrt(n)的约数，然后分别作n1,n2尝试是否可行。
算x一定要取模。否则1会变成n+1。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> using namespace std; const int maxn = 100000 + 10; int res[maxn]; int n,m,cnt; long long t,j; int main() { cin >> n; cnt=0; if(n==1) {printf("None\n"); return 0;} m=(int) sqrt(n+0.5); for(int i=1;i<=m;i++) if(n%i==0) { j=n/i; for(t=j;t<=n;t+=j) { if((t-2)%i==0) res[++cnt]=(t-1)%n; if((t+2)%i==0) res[++cnt]=(t+1)%n; } } sort(res+1,res+cnt+1); for(int i=1;i<=cnt;i++) if(res[i]!=res[i-1]) printf("%d\n",res[i]); return 0; }
原文：http://www.cnblogs.com/invoid/p/5617090.html