給定p,k,a,其中p,k是素數，求x^k=a (mod p)。 傳說中的much simpler task。。。。 設r是p的原根，（素數都有原根） 那麼r^1,r^2...r^phi(p)構成模p的完全剩余系， 故可設x=r^i ，a=r^j，那麼等式化成 r^(i*k)=r^j (mod p) 那麼由定理可得 i*k=j (mod p-1) 由r^j=a mod p 可由離散對數求得j 由i*k=j mod p-1 可由模線性方程求得i 由x=r^i 求得x 然後對所有x取余後排序，輸出即可。 [cpp] #include<map> #include<cstdio> #include<cmath> #include<vector> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; vector<ll>f,as; ll pow(ll a,ll b,ll mod){ ll as=1; while(b){ if(b&1)as=(as*a)%mod; a=(a*a)%mod;b>>=1; } return as; } bool g_test(ll g,ll p){ for(ll i=0;i<f.size();i++) if(pow(g,(p-1)/f[i],p)==1) return 0; return 1; } ll yuangen(ll p){ f.clear(); ll tmp=p-1; for(ll i=2;i<=tmp/i;i++) if(tmp%i==0){ f.push_back(i); while(tmp%i==0) tmp/=i; } if(tmp!=1)f.push_back(tmp); ll g=0; while(++g) if(g_test(g,p)) return g; } ll discrete_log(ll x,ll n,ll m){//x^y=n (mod m) 求 y map<ll,int>rec; ll s=(ll)(sqrt(m)+0.5); ll cur=1; for(int i=0;i<s;i++){ rec[cur]=i; cur=cur*x%m; } ll mul=cur; cur=1; for(int i=0;i<s;i++){ ll more=n*pow(cur,m-2,m)%m; if(rec.count(more))return i*s+rec[more]; cur=cur*mul%m; } return -1; } ll ex_gcd(ll a,ll b,ll& x,ll& y){ if(b==0){ x=1;y=0; return a; } else{ ll r=ex_gcd(b,a%b,y,x); y-=x*(a/b); return r; } } void line_mod_equation(ll a,ll b,ll n){//ax=b (mod n) 求x ll x,y,d;as.clear(); d=ex_gcd(a,n,x,y); if(b%d==0){ x%=n;x+=n;x%=n; as.push_back(x*(b/d)%(n/d)); for(ll i=1;i<d;i++) as.push_back((as[0]+i*n/d)%n); } } int main(){ ll a,k,p,g,q; while(~scanf("%lld%lld%lld",&p,&k,&a)){ if(a==0){puts("1\n0");continue;}//a==0特判 g=yuangen(p); q=discrete_log(g,a,p); line_mod_equation(k,q,p-1); for(int i=0;i<as.size();i++) as[i]=pow(g,as[i],p); sort(as.begin(),as.end()); printf("%d\n",as.size()); for(int i=0;i<as.size();i++) printf("%lld%c",as[i],i==as.size()-1?'\n':' '); } return 0; }
