51nod 1247 可能的路径(gcd)

传送门

题意

略

分析

有以下结论
(1.(x,y)->(y,x))
(2.(x,y)->(a,b)==>(a,b)->(x,y))
证明
做如下变换
((a,b)->(a-b,b)->(a-2b,b)->...->(a-nb,b)(n=a/b))
等效于
((a,b)->(a\%b,b)->(b,a\% b))
套用欧几里得算法，得到如下结论
如果gcd(a,b)==gcd(c,d),输出Yes,否则输出No