codevs 1213 解的个数

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 黄金 Gold

题目描述 Description

已知整数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。均不超过108。

输出描述 Output Description

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

样例输入 Sample Input

2

2 3 -7 0 10 0 10

1 1 1 -10 10 -9 9

样例输出 Sample Output

1

19

数据范围及提示 Data Size & Hint

 

exgcd

变量名重复了，卡了好久 。

mmp坑人的数据 专门卡通过率。。

屠龙宝刀点击就送

#include <ctype.h>
#include <cstdio>
typedef long long LL;
void read(LL &x)
{
    x=0;bool f=0;
    register char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=1;
    for(; isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
    x=f?(~x)+1:x;
}
LL n,a,b,c,p,q,r,s,ans;
LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    LL v=exgcd(b,a%b,x,y);
    LL tmp=x;x=y;y=tmp-a/b*y;
    return v;
}
int main()
{
    read(n);
    for(;n--;)
    {
        ans=0;
        read(a);read(b);read(c);read(p);read(q);read(r);read(s);c=(~c)+1;
        if((a==0&&b==0&&c!=0)||((p>q)||(r>s))) {printf("0
");continue;}
        if(a==0&&b==0&&c==0) {ans=(q-p+1)*(s-r+1);printf("%lld
",ans);continue;}
        LL x,y,g=exgcd(a,b,x,y);
        if(c%g) {printf("0
");continue;}
        LL x0=x*c/g,y0=y*c/g;
        for(LL i=-1000000;i<=1000000;i++)
        {
            LL m=x0+b/g*i,n=y0-a/g*i;
            if(m>=p&&m<=q&&n>=r&&n<=s) ans++;
        }
        printf("%lld
",ans);
    }
    return 0;
}