51Nod--1247 可能的路径(gcd)
根据规则可知 假设 (a,b) 可以到达坐标(aa,bb) 那么 aa=a*x+b*y x y 必定有解 所以 我们只要求两个坐标的gcd看是否相等就好
#include<bits/stdc++.h> using namespace std; #define maxn 50005 #define LL long long //LL a[maxn],b[maxn],ans=0; priority_queue<int,vector<int>,greater<int> >q; LL gcd(LL a,LL b){ return b==0? a:gcd(b,a%b); } int main(){ int t; cin>>t; while(t--){ LL x,y,xx,yy; cin>>x>>y>>xx>>yy; if(gcd(x,y)==gcd(xx,yy)){ cout<<"Yes"<<endl; }else{ cout<<"No"<<endl; } } return 0; }