[hiho1584]Bounce

题意：找出图中经过一次的格子个数。

这里写图片描述

解题关键：

组合数学的思想：先找出总的经过格子的次数，然后减去2倍的经过2次的格子个数。

1、总的求法：将长延展，当延展到n倍时，能够恰好到达右边的两个端点，则总格数可求出。

2、重复算法：可以找规律得到，途中会被划分成无数个小的正方形，对小正方形的边长进行分析，边长即为gcd，即可得到结论。

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<iostream>
 7 using namespace std;
 8 typedef long long ll;
 9 int main(){
10     ios::sync_with_stdio(0);
11     ll n,m;
12     while(cin>>n>>m){
13         n--,m--;
14         ll g=__gcd(n,m);
15         ll ans=n*m/g+1;
16         ans-=(n/g-1)*(m/g-1);
17         cout<<ans<<"\n";
18     }
19     return 0;
20 }