The number x is called an idempotent modulo n if x* x = x (mod n) Write the program to find all idempotents modulo n, where n is a product of two distinct primes p and q. Input First line contains the number k of test cases to consider (1 ≤ k ≤ 1000). Each of the following k lines contains one number n < 10 9 . Output Write on the i-th line all idempotents of i-th test case in increasing order. Only nonnegative solutions bounded by n should be printed. Example input output 3 6 15 910186311 0 1 3 4 0 1 6 10 0 1 303395437 606790875
题意：求出x = x*x (mod n)的解首先0 1肯定为一解 将条件转化成 x(x-1)%n = 0， 即 x(x-1)%pq = 0 => x(x-1) = ab*pq, a，b为整数 此时令x = ap, x-1 = bq, 则有 ap - bq = x - (x-1) = 1。 此时用欧几里得扩展就可以求出a，b的值进而求出x，即ap。 当x = aq, y = bp时也是同理。一共四组解
AC代码：
#include<iostream> #include<string> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include <queue> #include<sstream> #include <stack> #include <set> #include <bitset> #include<vector> #define FAST ios::sync_with_stdio(false) #define abs(a) ((a)>=0?(a):-(a)) #define sz(x) ((int)(x).size()) #define all(x) (x).begin(),(x).end() #define mem(a,b) memset(a,b,sizeof(a)) #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) #define rep(i,a,n) for(int i=a;i<=n;++i) #define per(i,n,a) for(int i=n;i>=a;--i) #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; typedef long long ll; typedef pair<ll,ll> PII; const int maxn = 5e4; const int inf=0x3f3f3f3f; const double eps = 1e-7; const double pi=acos(-1.0); const int mod = 1e9+7; inline int lowbit(int x){return x&(-x);} ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){if(!b){d=a,x=1,y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d); inline ll qpow(ll a,ll b,ll MOD=mod){ll res=1;a%=MOD;while(b>0){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;} inline ll inv(ll x,ll p){return qpow(x,p-2,p);} inline ll Jos(ll n,ll k,ll s=1){ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;} inline ll read(){ ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'|ch<'0') {if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0', ch = getchar();return x*f; } int dir[4][2] = { {1,0}, {-1,0},{0,1},{0,-1} }; ll prime[maxn]; ll vis[maxn]; ll tot = 0; void Prime() { prime[tot++] = 2; vis[4] = 1; for(int i=3; i <= maxn; i+=2) { if(vis[i]==0) prime[tot++]= i; for(int j=0;j<tot&&prime[j]*i<=maxn;j++) { vis[prime[j]*i] = 1; if(i%prime[j]==0) break; } } } bool IsPrime(ll k) { ll m = sqrt(k*1.0); rep(i,2,m) { if(k%i==0) return false; } return true; } int main() { int kase; cin>>kase; Prime(); while(kase--) { ll n; ll p , q, x, y,d; n = read(); rep(i,0,tot-1) { if(n%prime[i]==0&&IsPrime(n/prime[i])) { p = prime[i]; q = n / prime[i]; break; } } ex_gcd(p,q,d,x,y); ll res1 = (p * x+ n)%n ; ex_gcd(q,p,d,x,y); ll res2 = (q*x + n) %n; if(res1>res2) swap(res1,res2); printf("0 1 %lld %lld\n",res1,res2); } return 0; }