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

网友回答

算法主要是推出函数 f[m][n] = m + n - great_mon_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__div(int a,int b)
{if(a==0) return b;
if(b==0) return a;
if(!(a&1)&&!(b&1))return gre__div(a>>1,b>>1)1,b);
else if(!(b&1)) return gre__div(a,b>>1);else return gre__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)\n,m+n-gre__div(m,n));
}return 0;
}