codevs 1213 解的个数
2018-06-17 22:53:17来源:未知 阅读 ()
1213 解的个数
已知整数x,y满足如下面的条件:
ax+by+c = 0
p<=x<=q
r<=y<=s
求满足这些条件的x,y的个数。
第一行有一个整数n(n<=10),表示有n个任务。n<=10
以下有n行,每行有7个整数,分别为:a,b,c,p,q,r,s。均不超过108。
共n行,第i行是第i个任务的解的个数。
2
2 3 -7 0 10 0 10
1 1 1 -10 10 -9 9
1
19
分类标签 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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 暴力+辗转相除法——N个数求和 2020-03-24
- 两个数的差 2019-10-16
- 统计字符的个数,能够组成几个acmicpc 2019-10-16
- 从“最简真分数的个数”谈起 2019-09-17
- 剑指offer11:输入一个整数,输出该数二进制表示中1的个数。 2019-08-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash