1.题目描述： 2.题意： x*x=x(mod n)，给定n，求出所有小于n的x，升序输出。
3.思路： 1）扩展欧几里得。【待补】 2）逆元+费马小定理。 我们来看一个平凡解——x=0。由于这个是看得出来的，我们就直接输出，然后看一个也是比较平凡的解——x=1。x=1是怎么来的呢？当x与n互质的时候，xx=x(mod n)->x=1(mod n) 那么在x<=n的范围内，x=1。顺着这个思路，我们想：x和n不互质呢？我们分别讨论一下：假设n=pq，则： 当gcd(x,n)=p时，有：x=1(mod q)，x=kp。 当gcd(x,n)=q时，有：x=1(mod p)，x=kq。 那么我们将x=kp/kq反代回式子（这里k不相等），那么我们用费马小定理分别求出两个k，然后计算x。最终就能得到另外的两个解啦~
4.代码：
//G #include<bits/stdc++.h> #define rep(i,a,b) for(int i=(a);i<(b);++i) using namespace std; typedef long long ll; inline ll read() { ll x=0,sign=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') sign=-1; for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0'; return x*sign; } inline ll qpow(ll a,ll b,ll mod) { ll res=1; while(b>0) { if(b&1) res=res*a%mod; a=a*a%mod; b>>=1; } return res%mod; } // ll n; inline bool is_prime(ll x) { ll t=sqrt(x); rep(i,2,t+1) if(!(x%i)) return false; return true; } inline void solve() { n=read(); ll t=sqrt(n),p=0,q=0,k=0,x1=0,x2=0; rep(i,2,t+1) if(!(n%i)&&is_prime(i)&&is_prime(n/i)) { p=i,q=n/i; break; } k=qpow(p,q-2,q); x1=k*p; k=qpow(q,p-2,p); x2=k*q; if(x2<x1) swap(x1,x2); printf("0 1 %lld %lld\n",x1,x2); } int main() { for(int QwQ=read();QwQ;QwQ--) solve(); return 0; }