求算法及程序 由1*1的正方形拼成的长宽分别为m*n的长方形,求长方形对角线穿过小正方形的个数.

题目

求算法及程序 由1*1的正方形拼成的长宽分别为m*n的长方形,求长方形对角线穿过小正方形的个数.

答案

算法主要是推出函数 f[m][n] = m + n - great_common_div(m,n)
#include
#include
#define abss(x) ((x)>(0)?(x):(-x))
#define mins(a,b) ((a)>(b)?(b):(a))
using namespace std;
int gre_com_div(int a,int b)
{
if(a==0) return b;
if(b==0) return a;
if(!(a&1)&&!(b&1))return gre_com_div(a>>1,b>>1)1,b);
else if(!(b&1)) return gre_com_div(a,b>>1);
else return gre_com_div(abss(a-b),mins(a,b));
}
int main()
{
int m,n;
while(scanf("%d %d",&m,&n),m,n) //input m,n and m,n!=0
{
printf("Cross %d square(s) ",m+n-gre_com_div(m,n));
}
return 0;
}