求算法及程序 由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)\n,m+n-gre_com_div(m,n));}return 0;}

我也是这个答案