很遗憾这次比赛打铁。
但还是想做完这场比赛的题目,所以看了出题人的题解,给自己写一个赛后补题。
本领有限,不能很快写完,佛系填坑吧。
题目难度评测
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 |