2017ICPC北京赛区网络赛 G Bounce(GCD,找规律)

╰半橙微兮° 2022-06-08 11:18 153阅读 0赞

**Bounce**

时间限制: 1000ms

单点时限: 1000ms

内存限制: 256MB

### 描述 ###

For Argo, it is very interesting watching a circle bouncing in a rectangle.

As shown in the figure below, the rectangle is divided into N×M grids, and the circle fits exactly one grid.

The bouncing rule is simple:

1. The circle always starts from the left upper corner and moves towards lower right.

2. If the circle touches any edge of the rectangle, it will bounce.

3. If the circle reaches any corner of the rectangle after starting, it will stop there.

![15059824541259-428.png][]

Argo wants to know how many grids the circle will go through only once until it first reaches another corner. Can you help him?

### 输入 ###

The input consists of multiple test cases. (Up to 105)

For each test case:

One line contains two integers N and M, indicating the number of rows and columns of the rectangle. (2 ≤ N, M ≤ 109)

### 输出 ###

For each test case, output one line containing one integer, the number of grids that the circle will go through exactly once until it stops (the starting grid and the ending grid also count).

样例输入

2 2
    2 3
    3 4
    3 5
    4 5
    4 6
    4 7
    5 6
    5 7
    9 15

**样例输出**

2
    3
    5
    5
    7
    8
    7
    9
    11
    39

**题意**：给你一个n行m列的方阵，从最左上角的方块出发，向右下角移动，每次撞到边缘方块就转向90度，如题目中的样例图那样，当走到四个角的任意一个角后就停止，问只经过了一次的方块的个数。

**思路**：很明显，这题就是找规律，一般第一反应都会想去找一个线性递推的关系式，但是这个递推式很难去找，至少我和我的队友都没有找到。那么就换一种思路。我们观察一下题目给的那幅图，n=9，从起点出发后往下走8格到达底端，然后再往上走8格到达顶端。m=15，从起点出发往右走14格到达右端，再往左走14格到达左端，所以说n-1和m-1是竖直方向和水平方向的一个移动单元。我们不难发现，线与线之间的密集程度是取决于gcd(n-1,m-1)的，因为如果该值很大，那么有些方块你不管怎么走都是走不到的，自己在纸上模拟几个例子便可理解。根据这个发现我们可以推出最外一层的边界上走过的方块之间的距离是2\*gcd(n-1,m-1)-1，那么也就是在边界上每2\*gcd(n-1,m-1)个格子就有一个走过的方块，所以边界上的走过的方块我们就可以求出来是(n+m)/gcd(n-1,m-1)，然后我们也可以根据线与线之间的密集程度取决于gcd(n-1,m-1)这一点推出在每两个“×”(经过两次的方块)之间是有gcd(n-1,m-1)-1个走过的方块的，那么我们可以把它的路径每gcd(n-1,m-1)个分一组，起点不算，那么每一组都会有1个在边界上的方块或者是一个“×”，然后其余的都是走过一次的方块，接下来我们要算出总路径，不难发现，(n-1)和(m-1)的最小公倍数+1(算上起点)就是总路径，所以我们用总路径除以gcd(n-1,m-1)就是我们把路径分的组数。然后这个组数减去边界上的走过的方块数+1(多减了一个起点)再除以二(每个"×"经过了两次)，得到的就是“×”的个数，然后我们用总路径减去“×”的个数，就是答案了。

ans=(m-1)\*(n-1) / gcd(n-1, m-1) + 1 - (((m-1)\*(n-1) / gcd(n-1, m-1) / gcd(n-1, m-1)) - (n+m-2) / gcd(n-1, m-1) + 1)) ;

#include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a%b); }
    int main()
    {
    	LL n, m;
    	while (scanf("%lld%lld", &n, &m) != EOF)
    	{
    		if (n > m)
    			swap(n, m);
    		n--;m--;
    		printf("%lld\n", m*n/gcd(n,m)+1-((m*n/gcd(n,m)/gcd(n,m))-(n+m)/gcd(n,m)+1));
    	}
    }

[15059824541259-428.png]: /images/20220608/adaf66e50ea44534b0154851ff618ea6.png