【逆元】
逆元（inv）
1.什么是逆元
当求解公式：(a/b)%m 时，因b可能会过大，会出现爆精度的情况，所以需变除法为乘法：
设c是b的逆元，则有b*c≡1(mod m)；
则(a/b)%m = (a/b)*1%m = (a/b)*b*c%m = a*c(mod m);
即a/b的模等于a*b的逆元的模；
逆元就是这样应用的；
2.求逆元的方法
(1).费马小定理
在 p 是素数的情况下，对任意整数 x 都有 xp≡x(mod)p 。
如果 x 无法被 p 整除，则有 xp−1≡1(modp) 。
可以在 p 为素数的情况下求出一个数的逆元， x∗xp−2≡1(modp) ， xp−2 即为逆元。
题目中的数据范围1<=x<=10^9，p=1000000007，p是素数；
所以x肯定就无法被p整除啊，所以最后就得出x^(p-2)为x的逆元啦。
复杂度O(logn)；
代码：
const int mod = 1000000009;
long long quickpow(long long a, long long b) {if (b < 0) return 0;long long ret = 1;a %= mod;while(b) {if (b & 1) ret = (ret * a) % mod;b >>= 1;a = (a * a) % mod;}return ret;
}
long long inv(long long a) {return quickpow(a, mod - 2);
}(2)扩展欧几里得算法求逆元
扩展欧几里得算法可以参考小白书；
百度百科-乘法逆元中有这样一个例子:
例如：4关于1模7的乘法逆元为多少？ 4X≡1 mod 7 这个方程等价于求一个X和K，满足 4X=7K+1 其中X和K都是整数。 求x，k就是扩展欧几里得算法了吧~可扩展欧几里得求逆元ax≡1(mod n)其中a，n互质；
复杂度：O(logn)；
代码：
ll extend_gcd(ll a, ll b, ll &x, ll &y) {if (b == 0) {x = 1, y = 0;return a;}else {ll r = extend_gcd(b, a % b, y, x);y -= x * (a / b);return r;}
}
ll inv(ll a, ll n) {ll x, y;extend_gcd(a, n, x, y);x = (x % n + n) % n;return x;
}
求1,2,...,N关于P的逆元（P为质数）
复杂度：O(N)
代码：
const int mod = 1000000009;
const int maxn = 10005;
int inv[maxn];
inv[1] = 1;
for(int i = 2; i < 10000; i++)inv[i] = inv[mod % i] * (mod - mod / i) % mod;如果是求阶乘的逆元呢？（阶乘数组：fac[ ]）
代码：
inv[maxn]=mod_pow(fac[maxn],mod-2);
for(ll i=maxn-1;i>=0;i--)inv[i]=(inv[i+1]*(i+1))%mod;
参考blog：
.html、
/%E9%80%86%E5%85%83.html。
【逆元】
逆元（inv）
1.什么是逆元
当求解公式：(a/b)%m 时，因b可能会过大，会出现爆精度的情况，所以需变除法为乘法：
设c是b的逆元，则有b*c≡1(mod m)；
则(a/b)%m = (a/b)*1%m = (a/b)*b*c%m = a*c(mod m);
即a/b的模等于a*b的逆元的模；
逆元就是这样应用的；
2.求逆元的方法
(1).费马小定理
在 p 是素数的情况下，对任意整数 x 都有 xp≡x(mod)p 。
如果 x 无法被 p 整除，则有 xp−1≡1(modp) 。
可以在 p 为素数的情况下求出一个数的逆元， x∗xp−2≡1(modp) ， xp−2 即为逆元。
题目中的数据范围1<=x<=10^9，p=1000000007，p是素数；
所以x肯定就无法被p整除啊，所以最后就得出x^(p-2)为x的逆元啦。
复杂度O(logn)；
代码：
const int mod = 1000000009;
long long quickpow(long long a, long long b) {if (b < 0) return 0;long long ret = 1;a %= mod;while(b) {if (b & 1) ret = (ret * a) % mod;b >>= 1;a = (a * a) % mod;}return ret;
}
long long inv(long long a) {return quickpow(a, mod - 2);
}(2)扩展欧几里得算法求逆元
扩展欧几里得算法可以参考小白书；
百度百科-乘法逆元中有这样一个例子:
例如：4关于1模7的乘法逆元为多少？ 4X≡1 mod 7 这个方程等价于求一个X和K，满足 4X=7K+1 其中X和K都是整数。 求x，k就是扩展欧几里得算法了吧~可扩展欧几里得求逆元ax≡1(mod n)其中a，n互质；
复杂度：O(logn)；
代码：
ll extend_gcd(ll a, ll b, ll &x, ll &y) {if (b == 0) {x = 1, y = 0;return a;}else {ll r = extend_gcd(b, a % b, y, x);y -= x * (a / b);return r;}
}
ll inv(ll a, ll n) {ll x, y;extend_gcd(a, n, x, y);x = (x % n + n) % n;return x;
}
求1,2,...,N关于P的逆元（P为质数）
复杂度：O(N)
代码：
const int mod = 1000000009;
const int maxn = 10005;
int inv[maxn];
inv[1] = 1;
for(int i = 2; i < 10000; i++)inv[i] = inv[mod % i] * (mod - mod / i) % mod;如果是求阶乘的逆元呢？（阶乘数组：fac[ ]）
代码：
inv[maxn]=mod_pow(fac[maxn],mod-2);
for(ll i=maxn-1;i>=0;i--)inv[i]=(inv[i+1]*(i+1))%mod;
参考blog：
.html、
/%E9%80%86%E5%85%83.html。