The equation SGU

题目链接：https://codeforces.com/problemsets/acmsguru/problem/99999/106

这个题是关于EXGCD特别好的一个题目。题目大意：有一个等式ax+by+c=0，输入a,b,c以及a的范围l1,r1和b的范围l2,r2，输出满足方程的整数解的个数。

题解:

　　ax+by+c=0。对这个方程，首先考虑特殊情况：

1，a=0&&b=0&c=0，任意一个x和y都可以满足，所以答案为(r1-l1+1)*(r2-l2+1)

2，a=0&&b=0，直接输出0

3，a=0，方程转换为by=-c，判断c是否为b的倍数，不是的话直接输出0。是的话在判断y的范围，如果在(l2,r2)中，答案就是（r1-l1+1）b=0同理。

4，ax+by=-c。尽量让a和b都大于0。如果说a<0的话那么将a变为正，再改变一下a的取值范围就好了，b大概差不多。将c移过去，并尽量保证-c大于等于0

5，ax+by=c，用exgcd求解。首先如果c不是gcd(a,b)的倍数，无解。否则将方程转换为a1x+b1y=c1。a1=a/gcd(a,b)，b,c同理。用exgcd可以求出x的解集为x0+kb,y的解集为y0-ka。然后根据范围求k的取值范围。

6，求范围时会用到两个函数floor和ceil。其中floor表示向上取整如果4.9--4（小于4.9的最大整数），ceil为向下取整，3.1---4大于3.1的最大整数。然后上界取小，下界取大即可。

code:

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) {

    return b ==  ? a : gcd(b, a % b);

}

ll exgcd(ll a,ll b,ll &x,ll &y){

    if (b==){

        x=,y=;

        return a;

    }

    ll d=exgcd(b,a%b,y,x);

    y-=a/b*x;

    return d;

}

int main()

{

    ll a, b, c;

    cin >> a >> b >> c;

    c=-c;

    ll l1, r1, l2, r2;

    cin >> l1 >> r1 >> l2 >> r2;

    if (c < ) {

        c = -c; a = -a; b = -b;

    }

    if (a < ) {

        a = -a; l1 = -l1; r1 = -r1; swap(l1, r1);

    }

    if (b < ) {

        b = -b; r2 = -r2; l2 = -l2; swap(r2, l2);

    }

    if (a ==  && b ==  && c == ){

        cout << (r1 - l1 + ) * (r2 - l2 + ) << endl;

        return ;

    }

    else if (a ==  && b == ) { cout <<  << endl; return ; }

    else if (b == ) {

        if (c % b ==  && (-c) / b <= r2 && (-c) / b >= l2) cout << r1 - l1 +  << endl;

        else cout <<  << endl;

        return ;

    }

    else if (a == ) {

        if (c % a ==  && (-c) / a <= r1 && (-c) / a >= l1) cout << r2 - l2 +  << endl;

        else cout <<  << endl;

        return ;

    }

    ll d = gcd(a, b);

    if (c % d != ) puts("");

    else {

        ll x,y;

//        c=-c;

        a/=d;b/=d;c/=d;

        exgcd(a,b,x,y);

        x=x*c;y=y*c;

//        cout<<a<<"--"<<b<<"=="<<c<<"--"<<d<<"==="<<x<<"--"<<y<<endl;

        double rr1,ll1,rr2,ll2;

        rr1=double(r1);ll1=double(l1);

        rr2=double(r2);ll2=double (l2);

        ll upx=floor((rr1-x)/b),downx=ceil((ll1-x)/b);

        ll upy=floor((y-ll2)/a),downy=ceil((y-rr2)/a);

        ll ans=min(upx,upy)-max(downx,downy)+;

        cout<<(ans<? :ans)<<endl;

    }

    return ;

}

补充Exgcd(int a,int b,int &x,int &y)的知识：

证明：ax+by=gcd(a,b)k。先计算ax+by=gcd(a,b)，求解后再成k即可。

　　　　 bx+(a%b)y=gcd(b,a%b)。

　　　a%b=a-(a/b)*b（这里的除为整数除法）

　带入拆开得bx+ay-(a/b)*by=gcd(b,a%b)=gcd(a,b)=ax+by，然后对应相等，x=y,y=x-(a/b)*b*y

求出的解的集合就是x:x0+kb，y:y0-ka

exgcd code:

void exgcd(int a,int b,int &x,int &y){

    if(b==) {x=,y=}

    else {

        exgcd(a,b,x,y);

        int t=x;

        x=y;y=t-a/b*y;

    }

}

Exgcd还可以用来求解逆元。证明过程用到了同余方程即ax%b=c，也可记为ax=c(modb)当c等与1时，x就是a的逆元。

求解过程：ax-b*y=1，带入exgcd中，x就是a的逆元，要求就是a和b必须互质。

巴特西

The equation SGU - 106

最新文章

热门文章