看到題目先自己操作一下，發現（a,b)->(a+b,b)->(b+a,a+b-b)=(b+a,a)->(b,a) 即坐標（a,b)與（b，a)可以互換； 又發現若a>b;（a,b)->…->(a%b,b)->(b,a%b) 然后就想到求最小公倍數的模板
LL gcd(LL a,LL b){ if(a%b==0) return b; return gcd(b,a%b);}于是發現gcd（a,b)=x, (a,b)->(x,x); 所以若起點與終點都化為（x,x)形式，若相等即可走到
#include <bits/stdc++.h>using namespace std;#define maxn 50010#define LL long longLL gcd(LL a,LL b){ if(a%b==0) return b; return gcd(b,a%b);}int main(){// freopen("1.txt","w",stdout); LL a,b,x,y; int T; cin>>T; while(T--) { cin>>a>>b>>x>>y; LL b1=gcd(a,b); LL b2=gcd(x,y); if(b1==b2) cout<<"Yes/n"; else cout<<"No/n"; }}新聞熱點
疑難解答
