Problem
在一个无限大的二维网格上,你站在(a,b)点上,下一步你可以移动到(a + b, b), (a, a + b), (a - b, b), 或者 (a, a - b)这4个点。 给出起点坐标(a,b),以及终点坐标(x,y),问你能否从起点移动到终点。如果可以,输出"Yes",否则输出"No"。 例如:(1,1) 到 (2,3),(1,1) -> (2,1) -> (2,3)。
Solution
1,3操作互逆,2,4同样如此,4,3,2操作可以交换位置,假设前一个大于后一个,前一个可以不断减去后一个知道比后一个小。
这就是一个求gcd,可知gcd相等就能走到。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| #include<iostream> #include<stdio.h> #include<algorithm> #include<map> #include<queue> #include<cstring> #include<stack> #define mem(ss) memset(ss,0,sizeof(ss)) typedef long long ll; typedef long double ld; typedef __int128 lll; const lll mod=1e36+1; #define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);} inline int read(){int data=0;char ch=0;while (ch<'0' || ch>'9') ch=getchar();while (ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data;} ll T,a,b,x,y; int main(){ io_opt; cin>>T; while(T--){ cin>>a>>b>>x>>y;
if(gcd(a,b)==gcd(x,y)){ cout<<"Yes\n"; } else{ cout<<"No\n"; } } return 0; }
|