之前说道模意义下开根号
貌似就剩这一个锅了
今天就mie了她
Question:
给定方程 x ^ n ≡ a (mod p) 求x (p为质数)
Solution:
仍然考虑枚举 发现无法优化
考虑拆分 发现左边全是x没法拆...
由于我们先解决了离散对数问题 所以考虑转化
把x和a都转化成指数形式就可以解决
于是问题就变为g^(bn) ≡ g^c(mod p)
由于p是质数 所以如果欧拉定理优化就是bn≡c(mod p-1)
先不考虑g的问题 如果知道c就直接逆元就好了
然后如果知道g c也可以由BSGS求出来
所以问题转化为 对于一个质数p 求出一个g 使得g的0~p-2次方与1~p-1一一对应
我们给这个东西起名为 原根
总体来说也是一种暴力 然后根据玄学证明(实际还是比较简单的,跟上面过程差不多) 可以得出
验证p-1所有的素因子p[i]是否都没有g ^ (p - 1 / p[i]) ≡ 1 等价于验证所有[1~p]的数是否完全剩余
Code:并没有代码
(啪!)
Code by 学姐
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 #include <ctime> 7 //#define ivorysi 8 #define MAXN 100005 9 #define eps 1e-7 10 #define mo 974711 11 using namespace std; 12 typedef long long int64; 13 typedef unsigned int u32; 14 typedef double db; 15 int64 A,B,C,G,eu; 16 int64 ans[MAXN],tmp[MAXN],R,L[MAXN],cntL; 17 int M; 18 struct node { 19 int next,num; 20 int64 hsh; 21 }E[MAXN]; 22 int head[mo + 5],sumE; 23 int64 fpow(int64 x,int64 c,int64 MOD) { 24 int64 res = 1,t = x; 25 while(c) { 26 if(c & 1) res = res * t % MOD; 27 t = t * t % MOD; 28 c >>= 1; 29 } 30 return res; 31 } 32 int primitive_root(int64 P,int64 eu) { 33 static int64 factor[1005]; 34 int cnt = 0; 35 int64 x = eu; 36 for(int64 i = 2 ; i <= x / i ; ++i) { 37 if(x % i == 0) { 38 factor[++cnt] = i; 39 while(x % i == 0) x /= i; 40 } 41 } 42 if(x > 1) factor[++cnt] = x; 43 for(int G = 2 ; ; ++G) { 44 for(int j = 1 ; j <= cnt ; ++j) { 45 if(fpow(G,eu / factor[j],P) == 1) goto fail; 46 } 47 return G; 48 fail:; 49 } 50 } 51 int64 gcd(int64 a,int64 b) { 52 return b == 0 ? a : gcd(b,a % b); 53 } 54 void ex_gcd(int64 a,int64 b,int64 &x,int64 &y) { 55 if(b == 0) { 56 x = 1,y = 0; 57 } 58 else { 59 ex_gcd(b,a % b,y,x); 60 y -= a / b * x; 61 } 62 } 63 int64 Inv(int64 num,int64 MOD) { 64 int64 x,y; 65 ex_gcd(num,MOD,x,y); 66 x %= MOD;x += MOD; 67 return x % MOD; 68 } 69 void add(int u,int64 val,int num) { 70 E[++sumE].hsh = val; 71 E[sumE].next = head[u]; 72 E[sumE].num = num; 73 head[u] = sumE; 74 } 75 void Insert(int64 val,int num) { 76 int u = val % mo; 77 for(int i = head[u] ; i ; i = E[i].next) { 78 if(val == E[i].hsh) { 79 E[i].num = num; 80 return; 81 } 82 } 83 add(u,val,num); 84 } 85 int Query(int64 val) { 86 int u = val % mo; 87 for(int i = head[u] ; i ; i = E[i].next) { 88 if(val == E[i].hsh) { 89 return E[i].num; 90 } 91 } 92 return -1; 93 } 94 int BSGS(int64 A,int64 C,int64 P) { 95 memset(head,0,sizeof(head));sumE = 0; 96 int64 S = sqrt(P); 97 int64 t = 1,invt = 1,invA = Inv(A,P); 98 99 for(int i = 0 ; i < S ; ++i) { 100 if(t == C) return i; 101 Insert(invt * C % P,i); 102 t = t * A % P; 103 invt = invt * invA % P; 104 } 105 int64 tmp = t; 106 for(int i = 1 ; i * S < P ; ++i) { 107 int x = Query(tmp); 108 if(x != -1) { 109 return i * S + x; 110 } 111 tmp = tmp * t % P; 112 } 113 } 114 bool Process(int64 A,int64 C,int64 P,int k) { 115 int64 MOD = 1,g; 116 for(int i = 1 ; i <= k ; ++i) MOD *= P; 117 cntL = 0; 118 if(C % MOD == 0) { 119 int64 T = (k - 1) / A + 1; 120 L[++cntL] = 0; 121 if(T < k) { 122 int64 num = fpow(P,T,MOD); 123 for(int i = 1 ; i * num < MOD ; ++i) L[++cntL] = i * num; 124 } 125 } 126 else if(g = gcd(C % MOD,MOD) != 1){ 127 int64 x = C % MOD; 128 int c = 0; 129 while(x % P == 0) ++c,x /= P; 130 if(c % A != 0) return false; 131 G = primitive_root(MOD / (C / x),eu / (C / x)); 132 eu /= C / x; 133 int e = BSGS(G,x,MOD / (C / x)); 134 g = gcd(A,eu); 135 if(e % g != 0) return false; 136 e /= g; 137 int64 s = Inv(A / g,eu / g) * e % (eu / g); 138 L[++cntL] = s; 139 while(1) { 140 if((L[cntL] + eu / g) % (eu * (C / x)) == L[1]) break; 141 L[cntL + 1] = L[cntL] + eu / g; 142 ++cntL; 143 } 144 for(int i = 1 ; i <= cntL ; ++i) { 145 L[i] = fpow(G,L[i],MOD) * fpow(P,c / A,MOD) % MOD; 146 } 147 } 148 else { 149 int e = BSGS(G,C % MOD,MOD); 150 g = gcd(A,eu); 151 if(e % g != 0) return false;e /= g; 152 int s = Inv(A / g,eu / g) * e % (eu / g); 153 L[++cntL] = s; 154 while(1) { 155 if(L[cntL] + eu / g >= eu) break; 156 L[cntL + 1] = L[cntL] + eu / g; 157 ++cntL; 158 } 159 for(int i = 1 ; i <= cntL ; ++i) L[i] = fpow(G,L[i],MOD); 160 } 161 if(!cntL) return false; 162 if(!M) { 163 M = cntL; 164 for(int i = 1 ; i <= M ; ++i) ans[i] = L[i]; 165 sort(ans + 1,ans + M + 1); 166 M = unique(ans + 1,ans + M + 1) - ans - 1; 167 R = MOD; 168 return true; 169 } 170 int tot = 0; 171 for(int i = 1 ; i <= M ; ++i) { 172 for(int j = 1 ; j <= cntL ; ++j) { 173 tmp[++tot] = (R * Inv(R,MOD) % (R * MOD) * (L[j] - ans[i]) + ans[i]) % (R * MOD); 174 tmp[tot] = (tmp[tot] + R * MOD) % (R * MOD); 175 } 176 } 177 R *= MOD; 178 sort(tmp + 1,tmp + tot + 1); 179 tot = unique(tmp + 1,tmp + tot + 1) - tmp - 1; 180 for(int i = 1 ; i <= tot ; ++i) ans[i] = tmp[i]; 181 M = tot; 182 return true; 183 } 184 void Solve() { 185 M = 0; 186 if(B % 2 == 0) { 187 int64 Now = 2;B /= 2; 188 if(C & 1) ans[++M] = 1; 189 else ans[++M] = 0; 190 191 while(B % 2 == 0) { 192 B /= 2; 193 Now *= 2; 194 int t = 0; 195 for(int i = 1 ; i <= M ;++i) { 196 if(fpow(ans[i],A,Now) == C % Now) tmp[++t] = ans[i]; 197 if(fpow(ans[i] + Now / 2,A,Now) == C % Now) tmp[++t] = ans[i] + Now / 2; 198 } 199 for(int i = 1 ; i <= t ; ++i) ans[i] = tmp[i]; 200 if(!t) goto fail; 201 M = t; 202 } 203 R = Now; 204 sort(ans + 1,ans + M + 1); 205 M = unique(ans + 1,ans + M + 1) - ans - 1; 206 } 207 for(int64 i = 3 ; i <= B / i ; ++i) { 208 if(B % i == 0) { 209 eu = (i - 1); 210 B /= i; 211 int num = i,cnt = 1; 212 while(B % i == 0) { 213 B /= i;eu *= i;num *= i;++cnt; 214 } 215 G = primitive_root(num,eu); 216 if(!Process(A,C,i,cnt)) goto fail; 217 } 218 } 219 if(B > 1) { 220 eu = B - 1; 221 G = primitive_root(B,eu); 222 if(!Process(A,C,B,1)) goto fail; 223 } 224 if(M == 0) goto fail; 225 sort(ans + 1,ans + M + 1); 226 for(int i = 1 ; i <= M ; ++i) { 227 printf("%d%c",ans[i]," "[i == M]); 228 } 229 return; 230 fail: 231 puts("No Solution"); 232 } 233 int main() { 234 #ifdef ivorysi 235 freopen("f1.in","r",stdin); 236 #endif 237 int T; 238 scanf("%d",&T); 239 while(T--) { 240 scanf("%lld%lld%lld",&A,&B,&C); 241 Solve(); 242 } 243 }