建站加盟/国际财经新闻
先分享2个式子
当模式左边有除法：
今天了解了2个，感觉这2个很棒~，尤其第一个：
1、$\dfrac {a} {b}\% m=\dfrac {a \%\left( b\cdot m\right) } {b}$ 要求：a能整除b。(不知道用了什么奇技淫巧。。。)
2、$\dfrac {a} {b}\% m=(a\cdot b^{m-2} )\%m$ 要求：gcd(b , m)== 1 且 m为素数 且 a能整除b (利用费小马定理)
b在模m 下存在逆元的条件： b与m互质( 即gcd(b,m) == 1 )。
求逆元又分三种方法，拓展欧几里得法，欧拉函数法，费小马法。从一般到特殊吧：
1、拓展欧几里得法：
要求：a与m互质。
代码：
void ext_gcd(int a, int b, int &d, int &x, int &y)
{
if(!b)
{
d = a;
x = 1;
y = 0;
}
else
{
ext_gcd(b, a%b, d, y, x);
y -= x*(a/b);
}
}
int mod_inverse(int a, int m)
{
int x, y,d;
ext_gcd(a, m, d, x, y);
return (m + x % m) % m;
}
2、欧拉函数法
要求：b与m互质。
令$\phi \left( m\right) $表示小于等于且与互素的正整数的个数。
如果b和m互质(逆元存在条件)，则有$b^{\phi \left( m\right)}\equiv 1\left( modm\right) $ 。即$b\ast b^{\phi \left( m\right)-1}\equiv 1\left( modm\right) $，$b^{\phi \left( m\right)-1} $即为b的逆元
特殊的，当m为质数的情况下 ，$\phi \left( m\right) =m-1$，即费小马定理。
重点在于求解欧拉值
利用欧拉函数的积性性质：
对任意的整数n，可以将他分解为$n=p_{1}^{k_{1}}\ast p_{2}^{k_{2}}\ast p_{3}^{k_{3}}... p_{m}^{k_{m}} $，其中pi为质数，
其中$\phi \left( n\right) =\phi \left( p_{1}^{k_{1}}\right) \ast \phi \left( p_{2}^{k_{2}}\right) ... \phi \left( p_{m}^{k_{m}}\right) $
最后转化为：$\phi \left( n\right) =n\ast \prod \left( p_{i}-1\right) / p_{i}$
代码：
int eurler_phi(int n)
{
int res = n;
for(int i = 2; i * i <= n; i++){
if(n % i == 0){
res = res / i * (i - 1);
while(n % i == 0) n /= i;
}
}
if(n != 1) res = res / n * (n - 1);
return res;
}
3、费小马定理法
要求：b与m互质，且 m为质数
在m是素数的情况下，对任意整数b都有$b^m \equiv b(mod)m$
如果b无法被p整除，则有$b^{m-1} \equiv 1(modm)$
可以在p为素数的情况下求出一个数的逆元，$b * b^{m-2} \equiv 1(mod m)$，$b^{m-2}$即为逆元。
代码：可用快速幂幂
来源：https://www.cnblogs.com/shawn-ji/p/5674772.html