The 2023 ICPC Asia Regionals Online Contest (2) (pintia.cn)

K Super-knight

题意

有一个士兵，起初在n*n的棋盘的左下角，每次向右移动a格，向上移动b格，当越过地图边界时，则到地图的另一边（类似于没有边界墙的贪吃蛇），对这个士兵能到达的格子做标记，所有被标记的格子中，离左下角格子最近的距离是多少。（假设最近的格子为$(x, y)$，就输出$(x - 1)^2+(y - 1)^2$ )

（ $2 \le n \le 10^{18}, 1 \le a,b \le 200$)

思路

可以得出，在经过n次移动后，一定回回到起始点，所以最终的路径一定是循环的。

但n太大，无法通过这样判断所有的被标记的点。

可以发现，在移动了若干次后，除非穿过地图边界，否则只会增加 与原点的距离。因此我们只需要考虑刚穿过地图边界的点 即可。这样可以省下很多时间：
（每次直接刚好跨出地图边界，设从$(nowx,nowy)$点开始跨，那么一大步就跨了大约$min(\frac{n}{a},\frac{n}{b})$步，而一共进行n小步就可以回到初始点完成一次循环，因此总共需要的大跨步的次数仅仅是 a ，b的数量级，于是我们就可以在规定的时间内完成计算）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
using namespace std;
#define int long long 
int a,b,n;
inline int dis(int x,int y){
	return (x * x  + y * y ); 
}
int cnt = 0;
signed main(){
	int t;
	cin>>t;
	while(t--){
		cin>>a>>b>>n;
		a = a % n;
		b = b % n;
		int nowa = a % n;
		int nowb = b % n;
		int minn = a * a + b * b;
		while(nowa !=0 || nowb != 0){
			cnt ++;
			if(nowa <=300 && nowb <=300) 
				minn = min(minn,dis(nowa,nowb));
			int k = min((n - nowa - 1) / a,(n - nowb - 1) / b) + 1;
			nowa = (nowa + a * k % n) % n;
			nowb = (nowb + b * k % n) % n;
			
		}
		cout<<"**"<<cnt<<endl;
		cout<<minn<<endl;

	}
	return 0;
}

L