【数论】同余问题

定义

两个整数a和b，除以一个大于1的自然数m所得余数相同，就称a和b对于模m同余或称a和b在模m下同余，即 a≡b（mod m）

定律

a≡a(mod d)
a≡b(mod d)→b≡a(mod d)
(a≡b(mod d),b≡c(mod d))→a≡c(mod d)

如果a≡x(mod d),b≡m(mod d),则

a+b≡x+m （mod d）
a-b≡x-m (mod d)
a*b≡x*m (mod d）

值得一提的是：不满足a/n≡b/n(mod d) 求解用逆元

费马小定理：

如果b和p互质则b^p≡b（mod p）

可用于：由此可得b^p-1≡1（mod p）结合求逆元方程b*x≡1（mod p）得到b^p-1≡b*x（mod p)

所以x≡b^p-2（mod p）结合快速幂求出x

扩展欧几里德

已知a, b求解一组x，y，使它们满足贝祖等式： ax+by = gcd(a, b) =d

void exgcd(int a,int b,int &d,int &x,int &y)
{
    int t;
    if(b==0)//当b=0时 gcd(a,b)=a
            //因为1*a+0*0=a 所以ax+by=gcd(a,b)有一组解为
            //x=1 y=0 
    {
        d=a;
        x=1;
        y=0; 
    }
    else
    {
        exgcd(b,a%b,d,x,y);
        t=x;//推导得公式 
        x=y;
        y=t-(a/b)*y;
    }
}

View Code

应用：

求解ax+by=c

设g=gcd(a,b) a1=a/g b1=b/g c1=c/g

用exgcd求a1*x1+b1*y1=1的整数解

那么a1*g*c1*x1+b1*g*c1*y1=c1*g 即a*c1*x1+b*c1*y1=c

所以x0=c1*x1 y0=c1*y1是一组解

可推得通解为x=x0+b1*t y=y0-a1*t t属于Z

PS：当gcd(a,b)不整除c的时候不满足上述过程

线性同余方程

对于给定的整数a,b,m 求一个整数x满足a*x≡b(mod m) 或者给出无解

方程可以改写成ax+my=b

定理：

a,b,m是整数且m>0 gcd(a,m)=d 如果d|b 则方程有d个mod m不同的解否则无解
若gcd(a,m)=1 则称ax≡1(mod m)的一个解为a mod m的逆

PS：对于特殊方程ax≡1(mod m) 当且仅当gcd(a,m)=1时才有解可用Exgcd解

例题：洛谷P1082：同余方程：https://www.luogu.org/problemnew/show/P1082

代码：

#include<iostream>
using namespace std;
int a,b,x,y;
void exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
int main()
{
    cin>>a>>b;
    exgcd(a,b,x,y);
    cout<<(x+b)%b;
}

View Code

乘法逆元

对于a/b mod p（b和p互质）

First 费马小定理：

如果b和p互质且b<p 则b^p≡b（mod p）

由此可得b^p-1≡1（mod p）结合求逆元方程b*x≡1（mod p）得到b^p-1≡b*x（mod p)

所以x≡b^p-2（mod p）结合快速幂求出x

#include<cstdio> 
#define ll long long
using namespace std;
int n,p;
inline ll ksm(ll a,ll b){
    ll ans=1;
    a%=p;
    while(b){
        if(b&1) ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans%p;
}
void write(ll x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);putchar(x%10^48);
}
int main(){
    scanf("%d%d",&n,&p);
    for(int i=1;i<=n;i++)
        write(ksm(i,p-2)),putchar('
');
    return 0;
}

View Code

Second 解不定方程:

如果只是b和p互质则通过解同余方程

解a*x≡1（mod p）等于解ax+py=1

因为p是质数所以gcd(a,p)=1;

即解ax+py=gcd(a,p) 用exgcd解x

#include<cstdio>
using namespace std;
int x,y;
void exgcd(int a,int b){
    if(!b){x=1,y=0;return ;}
    exgcd(b,a%b);
    int t=x;
    x=y,y=t-a/b*y;
}
void write(int x){
    if(x>9) write(x/10);
    putchar(x%10^48);
}
int main(){
    int n,p;
    scanf("%d%d",&n,&p);
    for(int i=1;i<=n;++i)
        exgcd(i,p),write((x%p+p)%p),putchar('
');
    return 0;
}

View Code

Third 线性递推:

#include<cstdio>
#define ll long long
using namespace std;
const int maxn=3e6+5;
ll inv[maxn]={0,1};
int main(){
    int n,p;
    scanf("%d%d",&n,&p);
    printf("1
");
    for(int i=2;i<=n;i++)
        inv[i]=(ll)p-(p/i)*inv[p%i]%p,printf("%d
",inv[i]);
    return 0;
}

View Code

中国剩余定理

对于多个x≡a_i(mod m_i)

M=∏ⁿ_i=1m_i M_i=M/m_i

t_i是线性同余方程M_i*t_i≡1(mod m_i)的一个解

x=∑ⁿ_i=1a_i*M_i*t_i

int intchina(int n)
{
    int Mi,x,y,d,ans=0;
    M=1;
    for(int i=1;i<=n;i++)
    M*=m[i];
    for(int i=1;i<=n;i++)
    {
        Mi=M/m[i];
        exgcd(Mi,m[i],d,x,y);
        ans=(ans+Mi*x*a[i])%M;
    }
    return (ans+M)%M;
}

View Code