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

上一篇:vue中select设置默认选中


下一篇:AC日记——可能的路径 51nod 1247