[bzoj5027][exgcd][乱搞]数学题

本文主要是介绍[bzoj5027][exgcd][乱搞]数学题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

4

题解

真是失了智写的什么辣鸡..
ex随便搞出一组解
然后瞎移范围
欢快re
拍了一晚上没出错
发现
我对拍没出0的情况..
然后被A=0或者B=0卡了一晚上.

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define LL long long
#define mx 200000000
using namespace std;
LL exgcd(LL a,LL b,LL &x,LL &y)
{if(a==0){x=0;y=1;return b;}else{LL tx,ty;LL d=exgcd(b%a,a,tx,ty);x=ty-(b/a)*tx;y=tx;return d;}
}
LL A,B,C,K;
LL u1,u2,v1,v2;
int main()
{scanf("%lld%lld%lld%lld%lld%lld%lld",&A,&B,&C,&u1,&u2,&v1,&v2);if(u1>u2||v1>v2){printf("0\n");return 0;}if(!A&&!B){if(C==0)printf("%lld\n",(LL)(u2-u1+1)*(v2-v1+1));else printf("0\n");return 0;}K=-C;LL x,y;if(A==0){if(K%B){puts("0");return 0;}if(K/B>=v1&&K/B<=v2)printf("%lld\n",u2-u1+1);else puts("0");return 0;}if(B==0){if(K%A){puts("0");return 0;}if(K/A>=u1&&K/A<=u2)printf("%lld\n",v2-v1+1);else puts("0");return 0;}LL d=exgcd(A,B,x,y);if(K%d!=0){printf("0\n");return 0;}x=(x*(K/d));
//  printf("%lld\n",(K-A*x)/B);if(x>u2){LL gg=abs(B/d),dis=x-u1;//相邻可行x相距的长度if(gg==0){printf("0\n");return 0;}x=x-(dis/gg)*gg;}else if(x<u1){LL gg=abs(B/d),dis=u2-x;if(gg==0){printf("0\n");return 0;}x=x+(ceil(double(dis/gg)))*gg;gg=abs(B/d),dis=x-u1;x=x-(dis/gg)*gg;}else{LL gg=abs(B/d),dis=x-u1;if(gg!=0)x=x-(dis/gg)*gg;}if(x>u2||x<u1){printf("0\n");return 0;}y=(K-A*x)/B;LL ln1=abs(A/d),ln2=abs(B/d);//相邻可行y相距的长度 相邻可行x相距的长度LL u=x+ln2;LL v=(K-A*u)/B;int op;if(v<y)op=0;//y随着x增大而减小 else op=1;//增大而增大if(op==0)//减小 {if(y<v1){printf("0\n");return 0;}if(y>v2){if(ln1==0){printf("0\n");return 0;}LL ad1=ceil(double(y-v2)/double(ln1)),ad2=(u2-x)/ln2;if(ad1>ad2){printf("0\n");return 0;}y=y-ln1*ad1;x=x+ln2*ad1;}if(y<v1||y>v2){printf("0\n");return 0;}LL can_go=min((ln2==0?999999999:(u2-x)/ln2),(ln1==0?999999999:(y-v1)/ln1));printf("%lld\n",can_go+1);}else{if(y>v2){printf("0\n");return 0;}if(y<v1){if(ln1==0){printf("0\n");return 0;}LL ad1=(v2-y)/ln1,ad2=(u2-x)/ln2;y=y+ln1*ad1;LL gg1=(y-v1)/ln1;y=y-ln1*gg1;ad1-=gg1;if(ad1>ad2){printf("0\n");return 0;}x=x+ln2*ad1;}if(y<v1||y>v2){printf("0\n");return 0;}LL can_go=min((ln2==0?999999999:(u2-x)/ln2),(ln1==0?999999999:(v2-y)/ln1));printf("%lld\n",can_go+1);}return 0;
}