BZOJ5027: 数学题

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

HINT

Source

一眼就能看出是扩欧

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

注意特殊情况的判断

注意这里

一定要先乘再除

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

#include<iostream>
#include<cstdio>
#include<cmath>
#define LL long long 
using namespace std;
const LL MAXN=1e6+10;
LL a,b,c,x1,x2,yy1,y2,x,y;
LL exgcd(LL a,LL b,LL &x,LL &y) {
    if(b==0){x=1,y=0;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==0&&b==0) {
        if(c==0) {printf("%lld",(LL)(x2-x1+1)*(y2-yy1+1));return 0;}
        else {printf("0");return 0;}
    }
    if(a==0){
        if(c%b) {printf("0");return 0;}
        if(c/b>=yy1&&c/b<=y2) {printf("%lld",x2-x1+1);return 0;}
        else {printf("0");return 0;}
    }
    if(b==0) {
        if(c%a) {printf("0");return 0;}
        if(c/a>=x1&&c/a<=x2) {printf("%lld",y2-yy1+1);return 0;}
        else {printf("0");return 0;}
    }
    LL r=exgcd(a,b,x,y);
    b=b/r;a=-a/r;//利用公式构造增量
    if(c%r) {printf("0");return 0;}
    x=x*c/r;y=y*c/r;
    LL xlower,xupper,ylower,yupper;
    if(b>0) xlower=ceil( (double)(x1-x)/b ) , xupper=floor( (double)(x2-x)/b );
    if(b<0) xlower=ceil( (double)(x2-x)/b ) , xupper=floor( (double)(x1-x)/b );
    if(a>0) ylower=ceil( (double)(yy1-y)/a ) , yupper=floor( (double)(y2-y)/a );
    if(a<0) ylower=ceil( (double)(y2-y)/a ) , yupper=floor( (double)(yy1-y)/a );
    LL ans=max(0, min(xupper,yupper) - max(xlower,ylower) + 1  );
    printf("%lld",ans);    

    return 0;
}


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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏落影的专栏

程序员进阶之算法练习(二十九)

29220
来自专栏Leetcode名企之路

布隆过滤器

之前读吴军《数学之美》的时候提到布隆过滤器,觉得蛮有意思的,所以总结一下。 在计算机中,判断一个元素是不是在一个集合中,通常是用hash来解决,这在数据量不大的...

32910
来自专栏nummy

Uninformed search Python实现【译】

图的搜索可以分为uninformed搜索和informed搜索,两者的区别是前者是的搜索是盲目的,它不知道目标节点在哪,而后者是启发式的搜索。

12120
来自专栏hanlp学习笔记

hanlp中的N最短路径分词

N-最短路径 是中科院分词工具NLPIR进行分词用到的一个重要算法,张华平、刘群老师在论文《基于N-最短路径方法的中文词语粗分模型》中做了比较详细的介绍。该算法...

16400
来自专栏C/C++基础

认识UML类关系——依赖、关联、聚合、组合、泛化

在学习面向对象设计时,类关系涉及依赖、关联、聚合、组合和泛化这五种关系,耦合度依次递增。关于耦合度,可以简单地理解为当一个类发生变更时,对其他类造成的影响程度,...

15120
来自专栏决胜机器学习

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(2)

PHP数据结构(十一)——图的连通性问题与最小生成树算法(2) (原创内容,转载请注明来源,谢谢) 再次遇到微信公众号限制字数3000字的问题。因此将...

453100
来自专栏逸鹏说道

小白眼中的AI之~Numpy基础

引入一下 Numpy模块, Numpy的数组使用可以查看一下帮助文档, Numpy的 array数组类型必须是一致的(后面会讲)

11340
来自专栏尾尾部落

[LeetCode]Palindrome Number回文

链接:https://leetcode.com/problems/palindrome-number/#/description 难度:Easy 题目:De...

13020
来自专栏数据结构与算法

1226 倒水问题

1226 倒水问题 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 有两个无刻...

29060
来自专栏每日一篇技术文章

OpenGL ES _ 着色器_ 顶点着色器详解

提醒广大网友,当你看到这篇文章的时候,以后写的关于OpenGL 更多的便是代码实战了!

87910

扫码关注云+社区

领取腾讯云代金券