///@author Sycamore, ZJNU; ///@date 8/6/2017 ///@ref stanford-acm-master #include<bits/stdc++.h> using namespace std; typedef long long ll; int mod(int a, int b) { return ((a%b) + b) % b; } int extended_euclid(int a, int b, int &x, int &y) { int xx = y = 0; int yy = x = 1; while (b) { int q = a / b; int t = b; b = a%b; a = t; t = xx; xx = x - q*xx; x = t; t = yy; yy = y - q*yy; y = t; } return a; } int mod_inverse(int a, int n) { int x, y; int g = extended_euclid(a, n, x, y); if (g > 1) return -1; return mod(x,n)==0?n:mod(x,n); } int main() { ios::sync_with_stdio(false); int T; cin >> T; while (T--) { int a, m; cin >> a >> m; int mi = mod_inverse(a, m); if (~mi)cout << mi; else cout << "Not Exist"; cout << "\n"; } return 0; }
原文：http://www.cnblogs.com/zjnu/p/7296280.html