1306 - Solutions to an Equation
2024-09-02 23:44:14
1306 - Solutions to an Equation
| Time Limit: 2 second(s) | Memory Limit: 32 MB |
You have to find the number of solutions of the following equation:
Ax + By + C = 0
Where A, B, C, x, y are integers and x1 ≤ x ≤ x2 and y1 ≤ y ≤ y2.
Input
Input starts with an integer T (≤ 10000), denoting the number of test cases.
Each case starts with a line containing seven integers A, B, C, x1, x2, y1, y2 (x1 ≤ x2, y1 ≤ y2). The value of each integer will lie in the range [-108, 108].
Output
For each case, print the case number and the total number of solutions.
Sample Input |
Output for Sample Input |
|
5 1 1 -5 -5 10 2 4 -10 -8 80 -100 100 -90 90 2 3 -4 1 7 0 8 -2 -3 6 -2 5 -10 5 1 8 -32 0 0 1 10 |
Case 1: 3 Case 2: 37 Case 3: 1 Case 4: 2 Case 5: 1 |
PROBLEM SETTER: JANE ALAM JAN
思路：扩展欧几里得；
这题再次让我重新认识了扩欧；其实这题只要分情况讨论下，用扩欧求出特解，然后二分找通解中
t 的范围然后看t重合的部分就行，有几个特殊情况讨论下，还有A，B系数的符号讨论下。
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<queue>
#include<stack>
#include<set>
#include<math.h>
using namespace std;
typedef long long LL;
LL gcd(LL n,LL m)
{
if(m==0)
{
return n;
}
else if(n%m==0)
{
return m;
}
else return gcd(m,n%m);
}
pair<LL,LL>P(LL n,LL m)
{
if(m==0)
{
pair<LL,LL>ask=make_pair(1,0);
return ask;
}
else
{
pair<LL,LL>an=P(m,n%m);
LL x=an.second;
LL y=an.first;
y-=(n/m)*x;
an.first=x;
an.second=y;
return an;
}
}
int main(void)
{
LL i,j,k;
scanf("%lld",&k);
LL s;
LL A,B,C,x1,x2,y1,y2;
for(s=1; s<=k; s++)
{
LL sum=0;
scanf("%lld %lld %lld %lld %lld %lld %lld",&A,&B,&C,&x1,&x2,&y1,&y2);
C=-C;
if(A==0&&B==0&&C!=0)
sum=0;
else if(A==0&&B==0&&C==0)
{
sum=(LL)(x2-x1+1)*(LL)(y2-y1+1);
}
else if(A==0)
{
if(C%B)
{
sum=0;
}
else
{
LL t=(C/B);
if(t>=y1&&t<=y2)
sum=(x2-x1+1);
else sum=0;
}
}
else if(B==0)
{
if(C%A)
{
sum=0;
}
else
{
LL t=(C/A);
if(t>=x1&&t<=x2)
sum=(y2-y1+1);
else sum=0;
}
}
else
{
if(A<0)
{
C=-C;
A=-A;
B=-B;
}
LL gc=gcd(abs(A),abs(B));
if(C%gc)
{
sum=0;
}
else if((LL)A*(LL)B>0)
{
A/=gc;
B/=gc;
C/=gc;
pair<LL,LL>ask=P((A),(B));
LL x=(LL)ask.first;
LL y=(LL)ask.second;
x*=C;
y*=C;
LL l=-1e9;
LL r=1e9;
LL id=1e9;
while(l<=r)
{
LL mid=(l+r)/2;
if(x+mid*B>=x1)
{
id=mid;
r=mid-1;
}
else l=mid+1;
}
l=-1e9;
r=1e9;
LL ic=1e9;
while(l<=r)
{
LL mid=(l+r)/2;
if(x+mid*B<=x2)
{
ic=mid;
l=mid+1;
}
else r=mid-1;
}
if(id>ic)
{
sum=0;
}
else if(id==ic)
{
LL xx=x+id*B;
if(xx>=x1&&xx<=x2)
{
LL yy=y-id*A;
if(yy>=y1&&yy<=y2)
{
sum=1;
}
}
else sum=0;
}
else
{
l=-1e9;
r=1e9;
LL ip=1e9,iq=1e9;
while(l<=r)
{
LL mid=(l+r)/2;
if(y-mid*A>=y1)
{
ip=mid;
l=mid+1;
}
else r=mid-1;
}
l=-1e9;
r=1e9;
while(l<=r)
{
LL mid=(l+r)/2;
if(y-mid*A<=y2)
{
iq=mid;
r=mid-1;
}
else l=mid+1;
}
if(ip<iq)
{
sum=0;
}
else
{ if(ic<iq||id>ip)
{
sum=0;
}
else
{
if(id<=iq&&ic>=ip)
{
sum=ip-iq+1;
}
else if(iq<=id&&ip>=ic)
{
sum=ic-id+1;
}
else if(iq>=id&&iq<=ic)
{
sum=ic-iq+1;
}
else if(id>=iq&&id<=ip)
{
sum=ip-id+1; }
}
}
}
}
else
{
A/=gc;
B/=gc;
C/=gc;
pair<LL,LL>ask=P(abs(A),abs(B));
LL x=(LL)ask.first;
LL y=(LL)ask.second;
y=-y;
x*=C;
y*=C;
LL l=-1e9;
LL r=1e9;
LL id=1e9;
while(l<=r)
{
LL mid=(l+r)/2;
if(x+mid*abs(B)>=x1)
{
id=mid;
r=mid-1;
}
else l=mid+1;
}
l=-1e9;
r=1e9;
LL ic=1e9;
while(l<=r)
{
LL mid=(l+r)/2;
if(x+mid*abs(B)<=x2)
{
ic=mid;
l=mid+1;
}
else r=mid-1;
}
if(id>ic)
{
sum=0;
}
else if(id==ic)
{
LL xx=x+id*abs(B);
if(xx>=x1&&xx<=x2)
{
LL yy=y+id*A;
if(yy>=y1&&yy<=y2)
{
sum=1;
}
}
else sum=0;
}
else
{
l=-1e9;
r=1e9;
LL ip=1e9,iq=1e9;
while(l<=r)
{
LL mid=(l+r)/2;
if(y+mid*A>=y1)
{
iq=mid;
r=mid-1;
}
else l=mid+1;
}
l=-1e9;
r=1e9;
while(l<=r)
{
LL mid=(l+r)/2;
if(y+mid*A<=y2)
{
ip=mid;
l=mid+1;
}
else r=mid-1;
}
if(ip<iq)
{
sum=0;
}
else
{ if(ic<iq||id>ip)
{
sum=0;
}
else
{
if(id<=iq&&ic>=ip)
{
sum=ip-iq+1;
}
else if(iq<=id&&ip>=ic)
{
sum=ic-id+1;
}
else if(iq>=id&&iq<=ic)
{
sum=ic-iq+1;
}
else if(id>=iq&&id<=ip)
{
sum=ip-id+1; }
}
}//printf("%lld %lld %lld %lld\n",ip,iq,id,ic);
}
}
}
printf("Case %lld: %lld\n",s,sum); }
return 0;
}
最新文章
- linux Mint18 backspace怎么不能连续删除
- aspnet webapi 跨域请求 405错误
- 常用CSS居中
- Echarts学习笔记之饼图
- redis 在linux下的安装
- cocos2dx js 3.2 热更新
- Apache Kafka源码分析 - autoLeaderRebalanceEnable
- for name in loop Shell
- (medium)LeetCode 222.Count Complete Tree Nodes
- CDOJ 1221 Ancient Go
- MYSQL数据库-其他
- 如何确定Kafka的分区数、key和consumer线程数
- css 选择其父元素下的某个元素
- 【原创】大数据基础之Benchmark（2）TPC-DS
- Page Lifecycle API
- 3.Liunx网络管理命令
- html css input定位 文本框阴影 灰色不可编辑
- Excel学习之图表创建
- Spring MVC中forward请求转发2种方式（带参数）
- Jmeter 中Cookie管理器的使用