今天我们来探讨逆元在ACM-ICPC竞赛中的应用，逆元是一个很重要的概念，必须学会使用它。
对于正整数和，如果有，那么把这个同余方程中的最小正整数解叫做模的逆元。
逆元一般用扩展欧几里得算法来求得，如果为素数，那么还可以根据费马小定理得到逆元为。
推导过程如下
求现在来看一个逆元最常见问题，求如下表达式的值（已知）
当然这个经典的问题有很多方法，最常见的就是扩展欧几里得，如果是素数，还可以用费马小定理。
但是你会发现费马小定理和扩展欧几里得算法求逆元是有局限性的，它们都会要求与互素。实际上我们还有一
种通用的求逆元方法，适合所有情况。公式如下
现在我们来证明它，已知，证明步骤如下
接下来来实战一下，看几个关于逆元的题目。
题目：http://poj.org/problem?id=1845
题意：给定两个正整数和，求的所有因子和对9901取余后的值。
分析：很容易知道，先把分解得到，那么得到，那么
的所有因子和的表达式如下
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<vector> using namespace std; typedef long long ll; typedef pair<int, int> P; const int MOD = 9901; int vis[10000]; vector<int> pri; vector<P> Div; ll mul(ll a, ll n, ll k) { if(n == 0) return 0; if(n == 1) return a % k; ll ans = mul(a, n/2, k); ans += ans; if(n & 1) ans += a; return ans % k; } ll pow(ll a, ll n, ll mod) { if(n == 0) return 1; ll ans = pow(a, n/2, mod); ans = mul(ans, ans, mod); if(n & 1) ans *= a % mod; return ans % mod; } void get_Prime() { int n = (int)sqrt((double)50000005); for(int i = 2; i <= n; i++) for(int j = i*2; j <= n; j += i) vis[j] = 1; for(int i = 2; i <= n; i++) if(!vis[i]) pri.push_back(i); } void get_div(ll x) { for(int i = 0; i < pri.size(); i++) { if(x % pri[i] == 0) { int num = 0; while(x % pri[i] == 0) { x /= pri[i]; ++num; } Div.push_back(P(pri[i], num)); } } if(x != 1) Div.push_back(P(x, 1)); } ll cal(ll p, ll n) { // a + a^1 + a^2 + a^3 + ... ... + a^n n++; ll M = (p-1)*MOD; return (pow(p, n, M) + M - 1) / (p - 1); } int main() { ll A, B; cin >> A >> B; get_Prime(); get_div(A); ll sum = 1; for(int i = 0; i < Div.size(); i++) { sum *= cal(Div[i].first, Div[i].second*B)%MOD; sum %= MOD; } cout << sum << endl; return 0; }
