codevs 1213 解的个数

1213 解的个数

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

已知整数x,y满足如下面的条件:

ax+by+c = 0

p<=x<=q

r<=y<=s

求满足这些条件的x,y的个数。

输入描述 Input Description

第一行有一个整数nn<=10),表示有n个任务。n<=10

以下有n行,每行有7个整数,分别为:a,b,c,p,q,r,s。均不超过108。

输出描述 Output Description

n行,第i行是第i个任务的解的个数。

样例输入 Sample Input

2

2 3 -7 0 10 0 10

1 1 1 -10 10 -9 9

样例输出 Sample Output

1

19

数据范围及提示 Data Size & Hint

分类标签 Tags 点此展开

神坑啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

以下内容摘自某大神的题解

1.首先我们可以很直观地看出来这是用扩展欧几里得算法解二元一次方程,但问题是我们所熟悉的扩欧能解的方程都是ax+by=gcd(a,b)形式的,而题目给出的是ax+by=-c形式。举个例子:

2x+4y=18,首先我们可以换成x+2y=9形式。9不是2和4的最大公约数1,但9是1的倍数,所以如果我们解出一组x,y满足x+2y=1,那么x和y都乘上9/1就是原方程的一组解了。如果c/gcd(a,b)==0,那么就没有整数解。

2.如今我们得到了一组x,y,根据扩欧定理的后续内容,适合的解系一定是(x+bk,y-ak),注意现在的a,b是简化后的方程的系数(拿上面提到的例子讲,现在a=1,b=2),枚举找在区间内的解的个数(组数)就好。

3.现在解决各种WA/TLE/RE问题:

(1)方程无解:c/gcd(a,b)==0,直接输出0;

(2)区间不合法:题目中没有保证区间左端点小于右端点,所以如果读入的区间不合法,直接输出0;

(3)a=0或b=0:

if((a==0)&&(y<r||y>s)) {printf("0\n");continue;}

     if((b==0)&&(x<p||x>q)) {printf("0\n");continue;}

因为不管加多少,x/y还是原来的味道……但是如果不加特判可能会导致TLE(这个跟代码具体的写法有关,我后面有用while循环,直接卡T了)

(4)a==0&&b==0:

RE的关键所在,因为gcd求出来是0……这个需要认真思考一下,如果c!=0,显然方程不成立,无解;如果c==0,x和y就可以任意取了,由乘法原理可得解的个数就是两个区间内部整数点的个数的乘积

if (c!=0)printf("0\n");

else

{

    ll cnt=(q-p+1)*(s-r+1);

    printf("%lld\n",cnt);

}         

continue;

(5)记得要开long long

两个神坑的数据点:

4

0 1 2 0 0 0 2

1 0 2 0 0 0 0

1 0 2 0 2 0 20

2 0 3 -10 10 -10 10

ans:0   0   0   0

4

0 0 0 -1 1 -1 1

0 0 0 1 -1 1 2

0 0 1 1 1 1 1

0 0 0 -3406792423987599 -23487749 23947250

ans:9   0   0   2753863780940000

  1 #include<iostream>
  2 #include<cstdio>
  3 using namespace std;
  4 long long int x,y;
  5 long long int tot=0;
  6 long long int a,b,c,p,q,r,s;
  7 long long int gcd(long long int a,long long int b)
  8 {
  9     if(b==0)
 10     return a;
 11     else
 12     return gcd(b,a%b);
 13 }
 14 long long int exgcd(long long int a,long long int b,long long int & x,long long int & y)
 15 {
 16     if(b==0)
 17     {
 18         x=1;
 19         y=0;
 20         return a;
 21     }
 22     long long int r=exgcd(b,a%b,x,y);
 23     long long int tmp;
 24     tmp=x;
 25     x=y;
 26     y=tmp-a/b*y;
 27     return r;
 28 }
 29 int main()
 30 {
 31     
 32     int n;
 33     scanf("%d",&n);
 34     for(int i=1;i<=n;i++)
 35     {
 36         tot=0;
 37         //scanf("%lld %lld %lld %lld %lld %lld %lld",&a,&b,&c,&p,&q,&r,&s);
 38         cin>>a>>b>>c>>p>>q>>r>>s;
 39         c=-c;
 40         if((a==0)&&(y<r||y>s))
 41         {
 42             printf("0\n");
 43             continue;
 44         }
 45          if((b==0)&&(x<p||x>q)) 
 46         {
 47             printf("0\n");
 48             continue;
 49         }
 50         
 51         if(p>q||r>s)
 52         {
 53             cout<<0<<endl;
 54             continue;
 55         }
 56         
 57         int gys=gcd(a,b);
 58         if(gys==0)
 59         {
 60             if (c!=0)
 61             {
 62                 printf("0\n");
 63                 continue;
 64             }
 65             else
 66             {
 67                    tot=(q-p+1)*(s-r+1);
 68                 printf("%lld\n",tot);
 69                 continue;    
 70             }
 71         }
 72         if(c%gys!=0)
 73         {
 74             cout<<0<<endl;
 75             continue;
 76         }
 77         exgcd(a,b,x,y);
 78         x=x*(c/gys);
 79         y=y*(c/gys);
 80         a=a/gys;
 81         b=b/gys;
 82         while(x>=p)
 83         {
 84             x=x-b;
 85             y=y+a;
 86         }
 87         while(x<p&&b!=0)
 88         {
 89             x=x+b;
 90             y=y-a;
 91         }
 92         while(x>=p&&x<=q&&y>=r&&y<=s)
 93         {
 94             tot++;
 95             x=x+b;
 96             y=y-a;
 97             if(x<p||x>q||y<r||y>s)
 98             break;
 99         }
100         printf("%lld\n",tot);
101     }
102     
103     return 0;
104 }

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏SeanCheney的专栏

《Pandas Cookbook》第01章 Pandas基础

公司网址,http://www.dunderdata.com(dunder是蒸馏朗姆酒的残留液体,取这个名字是类比数据分析过程) GitHub地址:https...

17520
来自专栏wym

2013年多校赛 hdu4607

   那么就考虑树上最长距离,树的直径, 如果访问的点大于树的直径就要走回头路,答案即多的数乘2加上原来树的直径

13350
来自专栏WD学习记录

Leetcode Palindrome Number

Determine whether an integer is a palindrome. An integer is a palindrome when it...

12160
来自专栏一个会写诗的程序员的博客

《Kotlin极简教程》第五章 Kotlin面向对象编程(OOP)一个OOP版本的HelloWorld构造函数传参Data Class定义接口&实现之写pojo bean定一个Rectangle对象封

We frequently create a class to do nothing but hold data. In such a class some s...

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

3027 线段覆盖 2

3027 线段覆盖 2  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解  查看运行结果 题目描述 Descript...

29860
来自专栏noteless

[十六]基础类型BigInteger简介

final int[] mag;保存数字的数据 字节序为大端模式,大端模式就是低地址存储高位

46440
来自专栏机器学习与自然语言处理

用只含一个链域的节点实现循环链表的双向遍历

通常来说,要实现循环双向链表,每个节点需要有两个链域:前驱和后继。现在的问题是:如何设计一种环形表,使表的每个结点只包含一个链域而又能够有效地对其进行两个方向的...

22650
来自专栏菩提树下的杨过

java:POI导出excel

POI是一个开源项目,专用于java平台上操作MS OFFICE,企业应用开发中可用它方便导出Excel. 下面是使用示例: 1、maven中先添加依赖项 1 ...

37260
来自专栏Script Boy (CN-SIMO)

软件工程个人作业01

题目:      像二柱子那样,花二十分钟写一个能自动生成三十道小学四则运算题目的 “软件”,要求:除了整数以外,还要支持真分数的四则运算(需要验证结果的正确...

23500
来自专栏机器学习入门

挑战程序竞赛系列(86):3.6极限情况(3)

挑战程序竞赛系列(86):3.6极限情况(3) 传送门:AOJ 2201: Immortal Jewels 翻译参考至hankcs: http://www....

235100

扫码关注云+社区

领取腾讯云代金券