题目链接: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 == 0 ? a : gcd(b, a % b); } ll exgcd(ll a,ll b,ll &x,ll &y){ if (b==0){ x=1,y=0; 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 < 0) { c = -c; a = -a; b = -b; } if (a < 0) { a = -a; l1 = -l1; r1 = -r1; swap(l1, r1); } if (b < 0) { b = -b; r2 = -r2; l2 = -l2; swap(r2, l2); } if (a == 0 && b == 0 && c == 0){ cout << (r1 - l1 + 1) * (r2 - l2 + 1) << endl; return 0; } else if (a == 0 && b == 0) { cout << 0 << endl; return 0; } else if (b == 0) { if (c % b == 0 && (-c) / b <= r2 && (-c) / b >= l2) cout << r1 - l1 + 1 << endl; else cout << 0 << endl; return 0; } else if (a == 0) { if (c % a == 0 && (-c) / a <= r1 && (-c) / a >= l1) cout << r2 - l2 + 1 << endl; else cout << 0 << endl; return 0; } ll d = gcd(a, b); if (c % d != 0) puts("0"); 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)+1; cout<<(ans<0? 0:ans)<<endl; } return 0; }
补充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==0) {x=1,y=0} 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的逆元。