蛋糕切割【数论，数学】

题目大意：

题目链接：http://10.156.31.134/contestnew.aspx?cid=128
求一个$n imes m$的矩阵的对角线经过格子的个数。

---

思路：

有一个显然的结论：当$n,m$互质时，该矩形的对角线不会经过任意格子之间的点。只会穿过边。反之，$n imes m$的矩阵对角线经过的节点集合为${(x,y)|xin ^*,yin ^*,frac{x}{frac{n}{(n.m)}}=frac{y}{frac{m}{(n.m)}}}$。
所以任意的$n,m$不互质的情况均可以拆分成$(n,m)$个相同的情况来求。
若$n,m$互质，为了从左下角到达右上角，它的对角线必然会向上$n$个格子，向右$m$个格子。减去重复的一个，所以必然会经过$n+m-1$个格子。
代入$n'=frac{n}{(n,m)},m'=frac{m}{(n,m)}$，答案即为$(n'+m'-1) imes (n,m)$。

---

代码：

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;

int a,b;

int main()
{
	scanf("%d%d",&a,&b);
	int gcd=__gcd(a,b);
	printf("%d",((a/gcd)+(b/gcd)-1)*gcd);
	return 0;
}