hihoCoder 1584 Bounce 【数学规律】 （ACM-ICPC国际大学生程序设计竞赛北京赛区(2017)网络赛）

题目链接：

　　http://hihocoder.com/problemset/problem/1584

题目大意：

　　一个n*m的格子图，一个球从(1,1)开始延右下45°走，遇到边就反弹，直到走到四个角之一停止，问一路上只经过1次的格子数。

　　(n,m<=10)

题目思路：

　　【数学规律】

　　首先，由于反弹特性，我把球从网格中移到网格格线的交点上，于是图成了(n-1)*(m-1)的网格，球为点，左上角为(0,0)右下角为(n-1,m-1)

　　然后将反弹操作变换成将网格对称折叠复制，如下图，这样就能知道，最后球停下来的时候一定位于([n-1,m-1],[n-1,m-1])（[]为最小公倍数）

　　所以我们知道了球一路上经过的格子总数为[n-1,m-1]+1（(0,0)也要考虑），令d=gcd(n-1,m-1)

　　再看重复经过的点，发现分别是d,2d,3d,...,其中还要扣掉位于边缘处的点（边缘处的点只可能经过一次）

　　也就是扣掉(n-1),2(n-1),...,和(m-1),2(m-1),..

　　所以总共经过多次的格子数为[n-1,m-1]/d-(n-1)/d-(m-1)/d+1（+1是因为(n-1,m-1)这个点不能算，不会出现重复扣是因为第一次重复的点就是终点）

　　最终答案就是[n-1,m-1]+1-([n-1,m-1]/d-(n-1)/d-(m-1)/d+1)

 /****************************************************

     Author : Coolxxx

     Copyright 2017 by Coolxxx. All rights reserved.

     BLOG : http://blog.csdn.net/u010568270

 ****************************************************/

 #include<bits/stdc++.h>

 #pragma comment(linker,"/STACK:1024000000,1024000000")

 #define abs(a) ((a)>0?(a):(-(a)))

 #define lowbit(a) (a&(-a))

 #define sqr(a) ((a)*(a))

 #define mem(a,b) memset(a,b,sizeof(a))

 const double EPS=0.00001;

 const int J=;

 const int MOD=;

 const int MAX=0x7f7f7f7f;

 const double PI=3.14159265358979323;

 const int N=;

 using namespace std;

 typedef long long LL;

 double anss;

 LL aans;

 int cas,cass;

 int n,m,lll,ans;

 LL gcd(LL a,LL b)

 {

     if(!b)return a;

     return gcd(b,a%b);

 }

 int main()

 {

     #ifndef ONLINE_JUDGE

     freopen("1.txt","r",stdin);

 //    freopen("2.txt","w",stdout);

     #endif

     int i,j,k;

     int x,y,z;

 //    for(scanf("%d",&cass);cass;cass--)

 //    init();

 //    for(scanf("%d",&cas),cass=1;cass<=cas;cass++)

     while(~scanf("%d",&n))

     {

         scanf("%d",&m);

         n--,m--;

         LL d=gcd(n,m);

         aans=1LL*n*m/d;

         aans=aans-aans/d+n/d+m/d;

         printf("%lld\n",aans);

     }

     return ;

 }

 /*

 //

 //

 */