很遗憾这次比赛打铁。
但还是想做完这场比赛的题目，所以看了出题人的题解，给自己写一个赛后补题。
本领有限，不能很快写完，佛系填坑吧。
题目难度评测
L. Traveling in the Grid World (Middle)
题解：
若 g c d ( n , m ) = 1 gcd(n,m)=1 gcd(n,m)=1，那么我们从 ( 1 , 1 ) (1,1) (1,1)直线走到 ( n , m ) (n,m) (n,m)就是答案了。
接下来，我们讨论 g c d ( n , m ) ! = 1 gcd(n,m)!=1 gcd(n,m)!=1的情形。
首先我们可以知道，转折点越多，它的最短隔断越长。
所以我们的抱负转折点数是一个。
即：
找到一个数对 ( x , y ) , s . t . g c d ( x , y ) = g c d ( n − x , m − y ) = 1 ， w h i l e x 2 + y 2 + ( n − x ) 2 + ( m − y ) 2 (x,y),s.t.gcd(x,y)=gcd(n-x,m-y)=1，while\sqrt{x^2+y^2}+\sqrt{(n-x)^2+(m-y)^2} (x,y),s.t.gcd(x,y)=gcd(n−x,m−y)=1，whilex2+y2 +(n−x)2+(m−y)2 最小。
我们可以得到一个结论：当我们最小化这个隔断和时， g c d ( x , y ) gcd(x,y) gcd(x,y)一定是 1 1 1；
证明：
假设这个点是C，满意AC+BC是最小的隔断和；假设AC中存在整数点D，一定有BD |
