扩展欧几里德--解的个数

解的个数

已知整数x,y满足如下面的条件:

　　ax+by+c = 0

　　p<=x<=q

　　r<=y<=s

求满足这些条件的x,y的个数。

输入描述 Input Description

第一行有一个整数n（n<=10），表示有n个任务。n<=10

以下有n行，每行有7个整数，分别为：a,b,c,p,q,r,s。均不超过10⁸。

输出描述

共n行，第i行是第i个任务的解的个数。

样例输入

2 3 -7 0 10 0 10

1 1 1 -10 10 -9 9

样例输出

#include<cstdio>
#include<cmath>
int x,y,a,b,c,n,g;
long long ans,p,q,r,s;
int exgcd(int a,int b,int *x,int *y)//拓展欧几里德； 
{
 if(b==0){*x=1;*y=0;return a;}
 int d=exgcd(b,a%b,x,y);
 int z=*x;*x=*y;*y=z-*y*(a/b);
 return d;
}
void zhao1(int x,int y)
{
 if((x<=q)&&(x>=p)&&(y>=r)&&(y<=s))ans++;
 if(x<=q){
  if(b/g>0){x+=b/g;y-=a/g;zhao1(x,y);}//别把zhao1 放外面，b/g=0时会被卡挂了； 
  else if(b/g<0){x-=b/g;y+=a/g;zhao1(x,y);}  
 }
}
void zhao2(int x,int y)
{
 if((x<=q)&&(x>=p)&&(y>=r)&&(y<=s))ans++;
 if (x>=p){
  if(b/g>0){x-=b/g;y+=a/g;zhao2(x,y);}
  else if(b/g<0){x+=b/g;y-=a/g;zhao2(x,y);}  
 }
}
int main()
{
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
 {
  ans=0;
  scanf("%d%d%d%I64d%I64d%I64d%I64d",&a,&b,&c,&p,&q,&r,&s);
  if(s<r||q<p){printf("%I64d
",ans);continue;}//x或y的可行域不存在时，结果为0； 
  if(a==0&&b==0&&c==0) //a,b,c均为0时 ，x，y可以是任意值； 
   {s=s-r+1;q=q-p+1;ans=q*s;printf("%I64d
",ans);continue;}
  if(a==0&&b==0&&c!=0) //a=b=0，c！=0时 ，无解； 
   {printf("%I64d
",ans);continue;}
  c=-c;                //将c调到等号右边； 
  g=exgcd(a,b,&x,&y);  //找到a，b的最大公因数；并且找到一组ax+by=1的一组解； 
  x*=c/g;y*=c/g;       //得到ax+by=c时 的一组解； 
  if(a*x+b*y!=c)       //等号可能不成立，例2 0 1 ； 
       {ans=0;printf("%ld
",ans);continue;}
  zhao1(x,y);          //分别向x变大和变小的方向找在[p，q] 之间的解； 
  zhao2(x,y);
  if((x<=q)&&(x>=p)&&(y>=r)&&(y<=s)) ans-=1;//x，y符合要求时，两次递归多加了一次； 
  printf("%I64d
",ans);
 }
 return 0;
}

View Code

//自认为要懂扩展欧几里德有点难，偷个懒，背个代码。。。。