题目给出了a和p后，其实要求的就是
b是p的倍数时一定无解
b不是p的倍数时，由费马小定理一定有解
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 ll qmi(ll a, ll k, ll p) { 5 ll res = 1; 6 while (k) { 7 if (k & 1) { //如果k的个位是1的话 8 res = res * a % p; 9 } 10 k >>= 1; 11 a = a * a % p; 12 } 13 return res; 14 } 15 int main() { 16 ios::sync_with_stdio(false); 17 cin.tie(0); 18 cout.tie(0); 19 int n; 20 cin >> n; 21 while (n--) { 22 ll a, p; 23 cin >> a >> p; 24 ll res = qmi(a, p - 2, p); 25 if (a % p) { 26 cout << res << endl; 27 } else { 28 cout << "impossible" << endl; 29 } 30 } 31 return 0; 32 }
参考资料：https://www.cnblogs.com/-citywall123/p/10673212.html