学习了元根的一些知识，哈哈。
总结一下：
几个概念：
阶：对于模数m和整数a，并且gcd(m,a)==1，那么定义a在模m下的阶r为满足ar=1 mod m的最小正整数。
性质1：r in [1,phi(m)] (由欧拉定理）
性质2：r | phi(m) ( ar=aphi(m) mod m，然后用反证法)
性质3：r 是整数a模m的阶当且仅当满足：1）ar=1 mod m 2) a r/p(r) ≠ 1 mod m (后面推前面也用反正法）。
元根：
如果对于一个模数m，存在一个数a，满足a在模m下的阶是phi(m)，那么就称a是模数m的一个元根。
性质：所有质数有元根（更一般的，2,4,pe,2pe有元根，p是奇质数）
元根应用
元根依靠离散对数，将对数运算引入了模数的缩系下。从而可以解决很多数论中关于指数的问题。
indga=indgb mod phi(m) <=> a=b mod m
indgak=k indga mod phi(m)
indgab=indga+indgb mod phi(m)
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <vector> 5 #include <algorithm> 6 using namespace std; 7 8 typedef long long dnt; 9 10 const int mod = 8543; 11 const int elen = 100010; 12 struct Hash { 13 int head[mod], val[elen], rat[elen], next[elen], etot; 14 void init() { 15 memset( head, 0, sizeof(head) ); 16 etot = 0; 17 } 18 void insert( int v, int r ) { 19 int k = v % mod; 20 etot++; 21 next[etot] = head[k]; 22 rat[etot] = r; 23 val[etot] = v; 24 head[k] = etot; 25 } 26 int query( int v ) { 27 int k = v % mod; 28 for( int t=head[k]; t; t=next[t] ) 29 if( val[t]==v ) return rat[t]; 30 return -1; 31 } 32 }hash; 33 34 int p, a, k; 35 int g, b; 36 vector<int> stk; 37 38 dnt mpow( dnt a, int b, int m ) { 39 dnt rt; 40 for( rt=1; b; b>>=1,a=(a*a)%m ) 41 if( b&1 ) rt=(rt*a)%m; 42 return rt; 43 } 44 void exgcd( int a, int b, int &d, dnt &x, dnt &y ) { 45 if( b==0 ) d=a, x=1, y=0; 46 else { 47 exgcd( b, a%b, d, y, x ); 48 y-=a/b*x; 49 } 50 } 51 int gcd( int a, int b ) { 52 return b ? gcd(b,a%b) : a; 53 } 54 int findroot( int n ) { // n is prime 55 if( n==2 ) return 1; 56 57 vector<int> pfac; 58 int maxi = (int)ceil(sqrt(n-1)); 59 int remain=n-1; 60 for( int i=2; i<=maxi; i++ ) { 61 if( remain%i==0 ) { 62 pfac.push_back(i); 63 while( remain%i==0 ) 64 remain/=i; 65 } 66 } 67 if( remain!=1 ) pfac.push_back( remain ); 68 for( int i=1; ; i++ ) { 69 bool ok = true; 70 for( int t=0; t<pfac.size(); t++ ) 71 if( mpow(i,(n-1)/pfac[t],n)==1 ) { 72 ok = false; 73 break; 74 } 75 if( ok ) return i; 76 } 77 } 78 dnt inv( int a, int n ) { 79 return mpow(a,n-2,n); 80 } 81 dnt ind( int g, int b, int n ) { // n is prime, g is root, return v in [0,n-1] 82 hash.init(); 83 int m = (int)ceil(sqrt(n-1)); 84 dnt s = 1; 85 for( int i=0; i<m; i++ ) { 86 if( s==b ) return i; 87 hash.insert( s, i ); 88 s = (s*g) % n; 89 } 90 int am = s; 91 s = b; 92 for( int i=m,j; i<n; i+=m ) { 93 s = (s*inv(am,n)) % n; 94 if( (j=hash.query(s))!=-1 ) 95 return i+j; 96 } 97 return -1; // impossible 98 } 99 void meq( int a, int b, int m ) { 100 stk.clear(); 101 int d = gcd(a,m); 102 if( b%d ) return; 103 int aa=a/d, bb=b/d, mm=m/d, dd; 104 dnt x0, y0; 105 exgcd( aa, mm, dd, x0, y0 ); 106 x0 = (x0%mm+mm)%mm; 107 for( dnt k=0; k<d; k++ ) 108 stk.push_back( (x0*bb+k*mm)%m ); 109 } 110 111 int main() { 112 scanf( "%d%d%d", &p, &k, &a ); // x^k = a mod p 113 if( a==0 ) { 114 printf( "1 0 " ); 115 return 0; 116 } 117 // find the root of p: g 118 g = findroot(p); 119 // ind a: b 120 b = ind( g, a, p ); 121 // kx=b mod phi(p) 122 meq( k, b, p-1 ); 123 // decode 124 for( int t=0; t<stk.size(); t++ ) 125 stk[t] = mpow( g, stk[t], p ); 126 sort( stk.begin(), stk.end() ); 127 // output 128 printf( "%d ", stk.size() ); 129 for( int t=0; t<stk.size(); t++ ) 130 printf( "%d ", stk[t] ); 131 printf( " " ); 132 }