首页 > 代码库 > 好题、趣题、麻烦题
好题、趣题、麻烦题
sgu 106:
这道题首先让我们解一个线性方程式ax+by=-c，用拓展欧几里得就可以搞定。但是它要求我们需要输出满足x1<=x<=x2，y1<=y<=y2的解的个数，这可就没那么简单了...
我一开始想记录x和y的边界值，但想了好久，分了n多种情况...因为太繁琐，最后索性放弃分情况，交了一发WA了。
看了某人的解题报告后，发现原来可以求满足x1<=x0+k*r1<=x2，y1<=y0-k*r2<=y2的k的个数。r1=lcm/a，r2=lcm/b，lcm=a*b*gcd(a,b)。
然后解解方程，算算区间相交长度就行了。
（ceil和floor函数要#include <cmath>，而cmath里有名字叫y1的函数，真蛋疼。不过其实只要把y1从全局拿到main函数内部就好）
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #define debug(x) cout<<#x<<" = "<<x<<endl 5 using namespace std; 6 typedef long long LL; 7 8 LL gcd(LL a,LL b) 9 {10 LL temp;11 if (a<0) a=-a; if (b<0) b=-b;12 while (b!=0) { temp=b; b=a%b; a=temp; }13 return a;14 }15 //传入的a,b要保证是互质的（因为最后a*1+b*0=1时要保证a为1）16 void _gcd(LL a,LL b,LL &x,LL &y)17 {18 if (b==0) { x=1,y=0; return; }19 _gcd(b,a%b,x,y);20 LL temp=y;21 y=x-a/b*y; x=temp;22 }23 int main()24 {25 LL a,b,c,x1,x2,y1,y2;26 LL x,y;27 LL tx1,tx2,ty1,ty2;28 cin>>a>>b>>c>>x1>>x2>>y1>>y2;29 LL r=gcd(a,b),r1,r2;30 if (a==0&&b==0)31 {32 if (c==0) cout<<(x2-x1+1)*(y2-y1+1)<<endl;33 else cout<<0<<endl;34 }35 else if (a==0||b==0)36 {37 if (a==0) swap(a,b),swap(x1,y1),swap(x2,y2);38 if (c%a!=0) cout<<0<<endl;39 else if (-c/a>=x1&&-c/a<=x2) cout<<(y2-y1+1)<<endl;40 else cout<<0<<endl;41 }42 else if (c%r!=0) printf("0\n");43 else44 {45 _gcd(a/r,b/r,x,y);46 x*=-c/r; y*=-c/r;47 r=a*b/r; r1=r/a; r2=r/b;48 tx1=x1-x; tx2=x2-x; if (r1<0) swap(tx1,tx2),tx1=-tx1,tx2=-tx2,r1=-r1;49 ty1=-y2+y; ty2=-y1+y; if (r2<0) swap(ty1,ty2),ty1=-ty1,ty2=-ty2,r2=-r2;50 tx1=ceil(double(tx1)/r1); tx2=floor(double(tx2)/r1);51 ty1=ceil(double(ty1)/r2); ty2=floor(double(ty2)/r2);52 tx1=max(tx1,ty1); tx2=min(tx2,ty2);53 if (tx2>=tx1) cout<<tx2-tx1+1<<endl;54 else cout<<0<<endl;55 }56 return 0;57 }
好题、趣题、麻烦题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。