CF982E Billiard

原题链接

奇妙的数论题
用对称的方法展开图形，问题就变成了求一条射线最先经过的点\((k_1n, k_2m)\)

懒得画图，盗用一下大佬画的图
那么就是求\(an + (y - x) = bm\)
即\(an + (-b)m = y - x\)
使用\(\mathtt{exgcd}\)求出\(a,b\)，注意将水平或垂直移动的情况特判以及方程无解的情况
同时为方便计算，当速度有负方向时，将整个平面镜像翻转，使速度均为正，记得最后给出答案时转换回来即可。

#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int N = 1e5 + 10; const int mod = 1073741824; inline int re() {	int x = 0;	char c = getchar();	bool p = 0;	for (; c < '0' || c > '9'; c = getchar())	p |= c == '-';	for (; c >= '0' && c <= '9'; c = getchar())	x = x * 10 + c - '0';	return p ? -x : x; } ll exgcd(ll a, ll b, ll& x, ll& y) {	if (!b)	{	x = 1; y = 0;	return a;	}	ll gcd = exgcd(b, a % b, y, x);	y -= a / b * x;	return gcd; } int main() {	int i, j, k, n, m, x, y, vx, vy;	n = re(); m = re(); x = re();	y = re(); vx = re(); vy = re();	if (!vx)//特判水平或垂直移动	{	if (!x || x == n)	~vy ? printf("%d %d", x, m) : printf("%d 0", x);	else	printf("-1");	return 0;	}	if (!vy)	{	if (!y || y == m)	~vx ? printf("%d %d", n, y) : printf("0 %d", y);	else	printf("-1");	return 0;	}	bool px = 0, py = 0;	if (!~vx)//负方向速度就翻转	x = n - x, px = 1;	if (!~vy)	y = m - y, py = 1;	ll ansx, ansy, gcd;	gcd = exgcd(n, m, ansx, ansy);	if ((x - y) % gcd)//无解	return printf("-1"), 0;	ansx *= (x - y) / gcd;//一组特解	ansy *= (x - y) / gcd;	ll MOD = m / gcd;	ansx = (ansx % MOD + MOD - 1) % MOD + 1;//将解落到正整数的范围	ansy = -((x - y) - ansx * n) / m;	ansx = (ansx & 1 ? n : 0);//根据奇偶判断在哪个角	ansy = (ansy & 1 ? m : 0);	if (px)//翻转回来	ansx = n - ansx;	if (py)	ansy = m - ansy;	printf("%lld %lld", ansx, ansy);	return 0; }