首页 > 代码库 > SGU106 The Equation

SGU106 The Equation

2024-07-20 07:32:34   218人阅读

题意：给定a,b,c,x1,x2,y1,y2（都是整数），求有多少组(x,y)满足ax+by+c=0，且x1<=x<=x2,y1<=y<=y2

ax+by+c=0即ax+by=-c

容易知道 ax+by所表示的数一定是a,b的最大公约数的倍数，而且由裴蜀定理得一定存在一组x0,y0使得ax0+by0=(a,b)。x0,y0可以用扩展欧几里得算法求出。

那么如果c不是(a,b)的倍数就无解，否则我们得到一组基本解(k*x0,k*y0)  (k=-c/(a,b))

所有满足要求的解都有这样的格式(k*(x0+t*b/(a,b)),k*(y0-t*a/(a,b))) t为参数

用x1,x2,y1,y2这四个边界确定参数的范围t1~t2，统计范围内有多少个整数即可。([t2+eps]-[t1-eps])

注意a,b=0的情况，a,b为负数时需要变号。

代码：

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6 typedef long long ll; 7 const double eps=1e-6; 8 ll a,b,c,x1,x2,y1,y2,p,X,Y; 9 ll k1,k2;10 ll Abs(ll x){return (x>0)?x:-x;}11 ll flo(double x){12     if (x>=0)     return (ll)x;13     return -((ll)(-x)+1);14 }15 ll exgcd(ll a,ll b,ll& x,ll& y){16     ll x_1,y_1,ans;17     if (b==0) {18         x=1;y=0;return a;19     }20     ans=exgcd(b,a%b,x_1,y_1);21     x=y_1;y=x_1-(a/b)*y_1;22     return ans;23 } 24 int main(){25     cin>>a>>b>>c>>x1>>x2>>y1>>y2;26     if (a==0 && b==0) if (c!=0) {cout<<0<<endl;return 0;} else {cout<<(ll)((x2-x1+1)*(y2-y1+1))<<endl; return 0;}27     if (a==0) {28         if (c%b==0) {29             ll t= (-c)/b;30             if (t>=y1 && t<=y2) cout<<(x2-x1+1)<<endl; else cout<<0<<endl;31         }else cout<<0<<endl;32         return 0;33     }34     if (b==0) {35         if (c%a==0) {36             ll t= (-c)/a;37             if (t>=x1 && t<=x2) cout<<(y2-y1+1)<<endl; else cout<<0<<endl;38         }else cout<<0<<endl;39         return 0;40     }41     p=exgcd(Abs(a),Abs(b),X,Y);42     if (a<0) X=-X; if (b<0) Y=-Y;43     if (c%p!=0) {cout<<0<<endl;return 0;}44     X=X*((-c)/p);Y=Y*((-c)/p);45     k1=b/p;k2=-a/p;46     double t1=((double)(x1-X))/((double)k1);47     double t2=((double)(x2-X))/((double)k1);48     double u1=((double)(y1-Y))/((double)k2);49     double u2=((double)(y2-Y))/((double)k2);50     double k,sj,xj;51     if (t1>t2) {k=t1;t1=t2;t2=k;}52     if (u1>u2) {k=u1;u1=u2;u2=k;}53     xj=(t1>u1)?t1:u1;54     sj=(t2<u2)?t2:u2;55     ll Sj,Xj;56     Xj=flo(xj-eps);57     Sj=flo(sj+eps);58     if (Xj>Sj) {cout<<0<<endl;return 0;}59     cout<<Sj-Xj<<endl;60     return 0;61 }

 

SGU106 The Equation


联系
我们