题解：CF1451D Circle Game
Havefunn
·
·
题解
题目
圆心在原点，半径为 d 的圆内有一枚棋子，初始位于 (0,0)。两人轮流行动，先手先走。每一步必须恰好执行以下一种操作：
移动后棋子仍须满足 $x^2 + y^2 \le d^2$。无法行动者输。双方均采用最优策略，判断谁获胜。
#### 思路
参考博弈题的常见思路，将点（图中在圆内且坐标为整数的点）分为必胜点和必败点。其中必败点即为无法进行下一步操作的点，必胜点则反。显然能走到必胜点都是必败点。
手画一个图即可发现，原点的输赢情况只与对角线 $y=x$ 上能到达的最后一个点的输赢情况有关，所以我们仅需判断此点即可。判断方法见代码。
#### 代码
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll t,d,k;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>t;
while(t--){
cin>>d>>k;
ll b=floor(sqrt((d*d)/2.0)); //y=x上离圆最近且在圆内的点的横纵坐标
ll c=(b/k)*k; //y=x离原点最远能到达的横纵坐标
if((c+k)*(c+k)+c*c<=d*d) //能否再走一步
cout<<"Ashish"<<'\n';
else
cout<<"Utkarsh"<<'\n';
}
return 0;
}
```