2017ICPC北京网络赛 G | hihocoder 1584 Bounce

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.

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的方格表里,小球从左上角开始弹弹弹直到再次弹到角落,求只经过一次的格子的数量。
思路:总路径长度-经过两次的格子数量*2。

直觉告诉我们这个斜边间隔和gcd有关。
考虑3*6的情况

尝试做镜面反射,注意到反射后共用了一列边界,猜得到相邻斜线距离为\[L=gcd(n-1,m-1)\]路径总长为\[lcm(n-1,m-1)+1\]

n=3,m=6时L=gcd(2,5)=1,n=9,m=15时L=gcd(8,14)=2。

再考虑经过两次的格子数量。
按行把两次点分成两类,如下图红色类和蓝色类。

此图中L=2,红色类从L+1行L+1列开始每隔2L格一行,2L格一列(注意边界不能算),故红色类个数为\[\lceil\frac{n-L-1}{2\times L}\rceil\times\lceil\frac{m-L-1}{2\times L}\rceil\]

蓝色类从2L+1行2L+1列开始每隔2L格一行,2L格一列(注意边界不能算),故蓝色类个数为\[\lfloor\frac{n-2}{2\times L}\rfloor\times\lfloor\frac{m-2}{2\times L}\rfloor\]

于是答案为\[\frac{(n-1)\times(m-1)}{L}+1-2\times(\lceil\frac{n-L-1}{2\times L}\rceil\times\lceil\frac{m-L-1}{2\times L}\rceil+\lfloor\frac{n-2}{2\times L}\rfloor\times\lfloor\frac{m-2}{2\times L}\rfloor)\]

代码:

#include<bits/stdc++.h>
#define rep(ii,x,y) for(int ii=(x);ii<(y);ii++)
#define F first
#define S second
#define pc __builtin_popcount
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;

ll n,m,l,fu,suml,ans;

ll gcd(ll a,ll b){
	ll c=a%b;
	while(c){
		a=b;b=c;c=a%b;
	}
	return b;
}

int main(){
	while(scanf("%lld %lld",&n,&m)==2){
		if(n>m)swap(n,m);
		l=gcd(n-1,m-1);
		suml=(n-1)*(m-1)/l+1;
		fu=((n+l-2)/(l*2))*((m+l-2)/(l*2))+((n-2)/(l*2))*((m-2)/(l*2));
		ans=suml-fu*2;
		printf("%lld\n",ans);
	}
	return 0;
}

 

“2017ICPC北京网络赛 G | hihocoder 1584 Bounce”的一个回复

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注