欧几里得、扩展欧几里得、同余

一、同余:
1。若整数a和整数b除以正整数m的余数相等,则称a,b模m同余,记作a≡b(mod m)。

2。费马小定理:若p是质数,则对于任意整数a,有ap ≡a(mod p)。

3。欧拉定理:若正整数a,n互质,则 aφ(n)≡1(mod n) ,其中φ(n)是欧拉函数。

4。若正整数a,n互质,则对于任意正整数b,有ab≡abmodφ(n)(mod n)。

很多问题要求我们对一个质数p取模后输出。面对乘方算式,我们可以先把 底数对p取模(底数不是p的倍数)、指数对φ(p)取模,再计算乘方。

若a,n不一定互质且b>φ(n)时,有ab≡abmodφ(n)+φ(n) (mod n)。
这意味着即使底数与模数不互质,我们也有办法把指数的规模缩小到容易计算的范围。

5。若正整数a,n互质,则满足ax≡1(mod n)的最小正整数x0是φ(n)的约数。

二、扩展欧几里得算法:
1。对于任意整数a,b,存在一对整数x,y,满足 ax+by=gcd(a,b)。
求解ax+by=gcd(a,b)的一组特解x0,y0,并返回gcd(a,b)。

int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y);
    int z=x;
    x=y;
    y=z-y*(a/b);
    return d;
}

int d=exgcd(a,b,x0,y0);

2。对于一般的方程ax+by=c,它有解当且仅当gcd(a,b)|c。
令d=gcd(a,b)。
其通解可以表示为:

x=c/d*x0+k*b/d;
y=c/d*y0-k*a/d;
k取遍整数集合。

x的最小非负整数解:

x=(x%(b/d)+(b/d))%(b/d);

y的最小非负整数解:

y=(y%(a/d)+(a/d))%(a/d);

三、乘法逆元:
遇到(a/b)%p
或者(a/b)%m
1。当模数p为质数时,bp-2即为b的模p乘法逆元。
2。只保证b,m互质时,可以通过求解同余方程b*x≡1(mod m)求得其逆元。

int inverse(int b,int m)
{
    int x,y;
    int d=exgcd(b,m,x,y);
    return (x%m+m)%m;
}

3。若b,m不互质时,b模m的逆元从概念上来说是不存在的,但是(a/b)%m仍然是有值的。
(a/b)%m=(a%(b*m))/b
注意:a和m的乘积可能会太大而溢出。
4。若p是个质数:
inv(a)=(p-p/a)inv(p%a)%p。
求t关于mod的逆元:
t<mod

LL inv(LL i)
{
    if(i==1)return 1;
    return (mod-mod/i)*inv(mod%i)%mod;
}

线性时间复杂度求n个数关于mod的逆元:

LL inv[maxn];
void getInv(LL n)
{
    inv[1]=1;
    for(int i=2;i<n;i++)
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}

四、线性同余方程:
标准形式:ax≡b(mod m)
转化为:ax + my = b
线性同余方程有解当且仅当gcd(a,m)|b。
用扩展欧几里得求解即可求得x的通解及最小非负整数解。

上一篇:git 一些常用操作


下一篇:牛客 197C 期望操作数