sgu106.The equation 拓展欧几里得 难度:0
2024-08-30 19:49:18
106. The equation
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
There is an equation ax + by + c = 0. Given a,b,c,x1,x2,y1,y2 you must determine, how many integer roots of this equation are satisfy to the following conditions : x1<=x<=x2, y1<=y<=y2. Integer root of this equation is a pair of integer numbers (x,y).
Input
Input contains integer numbers a,b,c,x1,x2,y1,y2 delimited by spaces and line breaks. All numbers are not greater than 108 by absolute value.
Output
Write answer to the output.
Sample Input
1 1 -3
0 4
0 4
Sample Output
4 思路:
1 使用欧几里得构造出一组解使ax+by=gcd(a,b),然后(明显c%gcd!=0无解.)两边同乘以(c/gcd)
2 设k1=a/gcd,k2=b/gcd,(x,y)为原方程一组解,那么((x-n*k1),(y+n*k2))也是解(n为任意数)
3 于是不断寻找满足x1<=x<=x2,y1<=y<=y2的解,计数
4 这道题会爆int
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int inf=0x7ffffff;
long long tx1,tx2,ty1,ty2,a,b,c,tx,ty,minn,maxn;
void limit(long long L,long long R,long long d){//注意取区间端点
if(d<0){L=-L;R=-R;d=-d;swap(R,L);}
minn=max(minn,(long long)ceil((double)L/d));
maxn=min(maxn,(long long)floor((double)R/d));
}
long long extgcd(long long a,long long b,long long &x,long long &y){
long long d=a;
if(b!=0){
d=extgcd(b,a%b,y,x);
y-=(a/b)*x;
}
else {
x=1;y=0;
}
return d;
}
int main(){
while(scanf("%I64d%I64d%I64d",&a,&b,&c)==3){
scanf("%I64d%I64d%I64d%I64d",&tx1,&tx2,&ty1,&ty2);
if(tx1>tx2||ty1>ty2){
puts("0");continue;
}
long long ans=0;
if(a==0&&b==0){
if(c==0)ans=(tx2-tx1+1)*(ty2-ty1+1);
}
else if(a==0&&b){
if(c%b==0&&(-c/b)>=ty1&&(-c/b)<=ty2){
ans=(tx2-tx1+1);
}
}
else if(b==0&&a){
if(c%a==0&&(-c/a)>=tx1&&(-c/a)<=tx2){
ans=(ty2-ty1+1);
}
}
else {
int d=extgcd(a,b,tx,ty);
if((-c)%d==0){
tx=-tx*c/d;
ty=-ty*c/d;
minn=-inf;maxn=inf;
limit(tx1-tx,tx2-tx,b/d);
limit(ty1-ty,ty2-ty,-a/d);
if(minn<=maxn)ans=maxn-minn+1;
}
}
printf("%I64d\n",ans);
}
return 0;
}
最新文章
- IT软件的编程方向 - 进阶者系列 - 学习者系列文章
- linux用户管理（二）
- php实验四
- sublime SublimeTmpl 添加vue模板
- 用Meta标签控制360浏览器默认极速模式打开自己的网站和正则表达式
- CentOS(九)--与Linux文件和目录管理相关的一些重要命令①
- 查看Unix系统是32位还是64位
- MySql的卸载问题
- 一位学长的ACM总结（感触颇深）
- jQuery之简单动画效果
- 2016"百度之星" - 资格赛（Astar Round1） Problem D
- 02 Learning to Answer Yes/No
- 71、django之Ajax续
- ATS缓存数据结构
- PHP 单例模式优点意义及如何实现
- Vue中的slot内容分发
- HDU--4825 Xor Sum (字典树）
- Tomcat启动时项目重复加载的问题
- 八大最安全的Linux发行版，具备匿名功能，做服务器的首选，web，企业服务器等
- dml语句和ddl语句 区别