NOIP模拟（10.19）T2 弹球

弹球

题目背景：

10.19 NOIP模拟T2

分析：数学 (gcd & lcm)

这个题，我也是······很绝望·······

找规律 + 推式子

首先，我们来看一下小球的运动过程，经过的点的位置，我们从从左到右建立x轴，从上到下建立y轴，那么小球的运动可以表示为

x轴：1 2 3 4 … m m - 1 m - 2 … 1 2 3 4 … m m - 1 m - 2 …

y轴：1 2 3 4 … n n - 1 n - 2 … 1 2 3 4 … n n - 1 n - 2 …

可以比较明确的就是，小球停止的位置满足横坐标为1或m，纵坐标为1或n，那么我们考虑该如何划分周期，我们先不看第一列的1和1，那么x轴的周期为(2 ~ m), (m - 1 ~ 1)长度均为m - 1,并且周期结尾是我们想要的标号1和m，同理，y轴可以划分为(2 ~ n),(n - 1 ~ 1)长度为n - 1,周期结尾也是我们想要的标号1和n，那么显然第一个满足条件的终点出现的位置当然就是lcm(n - 1, m - 1) + 1的位置了，

解决了路径长度，我们再来看可行的点有哪些，首先，比较我们知道对于类似于ax + by的式子所能得到的值，肯定就是gcd(a, b)的所有倍数，那么我们现在这个到处乱跑的路径会形成很多交点或者边界点，而这些交点，相邻之间的距离一定是gcd(n - 1, m - 1) + 1（包括了两个作为端点的交点），证明的话，最好可以手推一下，感性理解，比较理性的理解就是，你可以通过观察小球所经过的位置的横纵坐标发现，这些坐标要么是和为gcd(n - 1, m - 1)的倍数，要么差为gcd(n - 1, m - 1)的倍数，如果和差均为gcd(n - 1, m - 1)的倍数那么就说明这个点会被经过两次，显然满足这个条件说明x, y均为gcd(n - 1, m - 1)的倍数，那么显然每gcd(n - 1, m - 1)有一个，然后我们可以将这个路径的长度看做是lcm(n - 1, m - 1)将起点除去，然后每一条边看做是一条长为gcd(n - 1, m - 1)的边，每一条边的结束点为一个交点或者边界点，然后显然除了每一条边的两个端点其余点一定只经过了一次，那么这一部分点的贡献就是lcm(n - 1, m - 1) / gcd(n - 1, m - 1) * (gcd(n - 1, m - 1) - 1)(边数 * 每条边的可行点)，然后我们再来看边界上被我们排除的点，显然边界上的点满足横坐标为1，或者横坐标为m，或者纵坐标为1，或者纵坐标为n,回到我们之前写的轨迹，可以清楚的发现，这样的点的个数为lcm(n - 1, m - 1) / (n - 1) + lcm(n - 1, m - 1) / (m - 1) - 1 + 1,（终点横纵坐标都会满足条件，而其他边界点只可能满足一个，那么终点会被算两次，然后起点没有被算到所以加一减一相当于就是lcm(n - 1, m - 1) / (n - 1) + lcm(n - 1,  m - 1) / (m - 1), 至此此题完成答案为lcm(n - 1, m - 1) / gcd(n - 1, m - 1) * (gcd(n- 1, m - 1) - 1) + lcm(n - 1, m - 1) / (n - 1) + lcm(n - 1, m - 1) / (m - 1),O(logn)求出gcd即可。

Source：

/*
	created by scarlyw
*/
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <vector>
#include <queue>
#include <map>
#include <set>

inline char read() {
	static const int IN_LEN = 1024 * 1024;
	static char buf[IN_LEN], *s, *t;
	if (s == t) {
		t = (s = buf) + fread(buf, 1, IN_LEN, stdin);
		if (s == t) return -1;
	}
	return *s++;
}

/*
template<class T>
inline void R(T &x) {
	static bool iosig;
	static char c;
	for (iosig = false, c = read(); !isdigit(c); c = read()) {
		if (c == -1) return ;
		if (c == '-') iosig = true;
	}
	for (x = 0; isdigit(c); c = read()) x = ((x << 2) + x << 1);
	if (iosig) x = -x;
}
//*/

const int OUT_LEN = 1024 * 1024;
char obuf[OUT_LEN], *oh = obuf;
inline void write_char(char c) {
	if (oh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf;
	*oh++ = c;
}

template<class T>
inline void W(T x) {
	static int buf[30], cnt;
	if (x == 0) write_char('0');
	else {
		if (x < 0) write_char('-'), x = -x;
		for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
		while (cnt) write_char(buf[cnt--]);
	}
}

inline void flush() {
	fwrite(obuf, 1, oh - obuf, stdout);
}

///*
template<class T>
inline void R(T &x) {
	static bool iosig;
	static char c;
	for (iosig = false, c = getchar(); !isdigit(c); c = getchar()) {
		if (c == -1) return ;
		if (c == '-') iosig = true;
	}
	for (x = 0; isdigit(c); c = getchar()) x = ((x << 2) + x << 1) + (c ^ '0');
	if (iosig) x = -x;
}
//*/

long long n, m, t;

inline long long gcd(long long a, long long b) {
	return b ? gcd(b, a % b) : a;
}

inline void solve() {
	R(n), R(m), n--, m--;
	long long t = gcd(n, m), ans = n / t * m / t * (t - 1) + n / t + m / t;
	W(ans), write_char('\n');
}

int main() {
	R(t);
	while (t--) solve();
	flush();
	return 0;
}