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

样例输入

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;
}