扩展欧几里得例题

扩展欧几里得例题

ACM、数论admin发表留言

裴祖定理是求解未知数为p,q的pa+qb=gcd(a,b)的方程必然有整数解，那么求解这个方程就需要使用扩展欧几里得了。

例题1：HDU1576 A/B

题意：

给出n(n=A\mod9973)，求\frac{A}{B}\mod9973 (A必能被B整除)

做法

考虑带余除法\frac{A}{B}=9973\times k+x
\Rightarrow A=9973\times k\times B+x\times B
又由于n=A\mod9973
所以x\times B\equiv n (\mod9973)
问题转化为求x\times B-9973\times y=n的整数解
令x’=\frac{x}{n},y’=-\frac{y}{n}, 问题转化为求解Bx’+9973y’=1的整数解，由于gcd(9973,B)=1 可以用扩展欧几里得求解

代码
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
void gcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1;y=0;
        return;
    }
    gcd(b,a%b,x,y);
    ll tmp=x;
    x=y;
    y=tmp-a/b*x;
}
int main(){
    ll T;
    cin>>T;
    while(T--){
        ll n,b;
        cin>>n>>b;
        ll x,y;
        gcd(b,9973,x,y);
        x*=n;
        cout<<(x%9973+9973)%9973<<endl;
    }
    return 0;
}

例题2：51nod 1352 集合计数

题意

给出N个固定集合\lbrace 1，N\rbrace,\lbrace2, N-1\rbrace,\lbrace3,N-2\rbrace,\cdots,\lbrace N-1,2\rbrace,\lbrace N,1\rbrace.求出有多少个集合满足：第一个元素是A的倍数且第二个元素是B的倍数。

做法

设第一个元素是p，则有 A|p,B|n+1-p
设p=Am,n+1-p=Bn
则方程转化为Am+Bn=n+1中 满足0<Am\le n中m的个数（设该方程为1号方程）
我们先考虑Am+Bn=gcd(A,B)的整数解，设为m’与n’
则1号方程有特解 \frac{m’}{gcd(A,B)}\times(n+1)
1号方程所有的解可以表示为\frac{m’}{gcd(A,B)}\times(n+1)+\frac{B}{gcd(A,B)}t \quad (t\in Z)
(显然当(n+1)\mod gcd(A,B)\ne0时方程组无解，故直接输出0即可)
故问题转化为求解满足A(\frac{m’}{gcd(A,B)}\times(n+1)+\frac{B}{gcd(A,B)}t)\le n的t的个数

源代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,a,b,T,gcdab;
void gcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    {
        x=1;y=0;
        gcdab=a;
        return;
    }
    gcd(b,a%b,x,y);
    ll tmp=x;
    x=y;
    y=tmp-a/b*x;
}
ll cl(double xx,ll x){
    if(xx<0) return 0;
    return (ll)xx+(x!=0);
}
int main(){
    cin>>T;
    while(T--){
        ll x,y;
        cin>>n>>a>>b;
        gcd(a,b,x,y);
        if((n+1)%gcdab){cout<<0<<endl;
            continue;
        }
        x=(x%b+b)%b;
        x=x*(n+1)/gcdab;
        x%=(b/gcdab);
        double ans=((double)n/a-x)*gcdab/b;
        cout<<cl(ans,x)<<endl;
    }
    return 0;
}

总结

对于方程组ax+by=gcd(a,b)的求解来说，我们可以通过扩展欧几里得求得其中的一组特解x’,y’，所有的解可以x=x’+\frac{b}{gcd(a,b)}t\quad y=y’-\frac{a}{gcd(a,b)}t\quad t\in Z 来表示

留下回复