BZOJ5027: 数学题

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 140 Solved: 48
[Submit][Status][Discuss]

Description

给出a,b,c,x1,x2,y1,y2，求满足ax+by+c=0，且x∈[x1,x2],y∈[y1,y2]的整数解有多少对？

Input

第一行包含7个整数，a,b,c,x1,x2,y1,y2，整数间用空格隔开。

a,b,c,x1,x2,y1,y2的绝对值不超过10^8。

Output

输出整数解有多少对？

Sample Input

1 1 -3 0 4 0 4

Sample Output

HINT

Source

一眼就能看出是扩欧

利用扩欧的通项公式求出上下边界进行处理

注意特殊情况的判断

注意这里

一定要先乘再除

mmp调了一晚上拍了n组数据都没拍出错误来。。

#include<iostream>

#include<cstdio>

#include<cmath>

#define LL long long

using namespace std;

const LL MAXN=1e6+;

LL a,b,c,x1,x2,yy1,y2,x,y;

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

    if(b==){x=,y=;return a;}

    LL r=exgcd(b,a%b,x,y),tmp;

    tmp=x,x=y,y=tmp-a/b*y;

    return r;

}

LL min(LL a,LL b){return a<b?a:b;}

LL max(LL a,LL b){return a>b?a:b;}

int main()

{

    cin>>a>>b>>c>>x1>>x2>>yy1>>y2;c=-c;

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

        if(c==) {printf("%lld",(LL)(x2-x1+)*(y2-yy1+));return ;}

        else {printf("");return ;}

    }

    if(a==){

        if(c%b) {printf("");return ;}

        if(c/b>=yy1&&c/b<=y2) {printf("%lld",x2-x1+);return ;}

        else {printf("");return ;}

    }

    if(b==) {

        if(c%a) {printf("");return ;}

        if(c/a>=x1&&c/a<=x2) {printf("%lld",y2-yy1+);return ;}

        else {printf("");return ;}

    }

    LL r=exgcd(a,b,x,y);

    b=b/r;a=-a/r;//利用公式构造增量

    if(c%r) {printf("");return ;}

    x=x*c/r;y=y*c/r;

    LL xlower,xupper,ylower,yupper;

    if(b>) xlower=ceil( (double)(x1-x)/b ) , xupper=floor( (double)(x2-x)/b );

    if(b<) xlower=ceil( (double)(x2-x)/b ) , xupper=floor( (double)(x1-x)/b );

    if(a>) ylower=ceil( (double)(yy1-y)/a ) , yupper=floor( (double)(y2-y)/a );

    if(a<) ylower=ceil( (double)(y2-y)/a ) , yupper=floor( (double)(yy1-y)/a );

    LL ans=max(, min(xupper,yupper) - max(xlower,ylower) +   );

    printf("%lld",ans);    

    return ;

}

//1 5 -3 -123 40 -567 41

巴特西