基础内功心法

1.什么是最小公倍数以及什么是最大公约数?

最小公倍数(Least Common Multiple):两个或多个整数公有的倍数(就是这个两个及以上整数 乘以0以外的整数 产生相同的结果中最小的数值 就是他们的最小公倍数 )

最大公约数(Greatest Common Divisor): 同样是适用于两者或两者以上的除数(就是两个及以上的整数  除以0以外的整数 且可被整除的数   这些整数中最大的那一个  就是他们的最大公约数)

2.如何区分最大公约数和最小公倍数(口诀20字)

最大公约数是除出来的   最小公倍数是乘出来的

枚举:

int gcd(int x, int y)    //用小的值控制循环
{
	int t = 0;
	int i = 0;
	if (x > y)
	{
		t = x;
		x = y;
		y = t;
	}
	
	for (int i=x; i>=1; i--)
	{
		if (y%i==0 && x%i==0)
		{
			break;
		}
	}
	return i;
}

辗转反侧:

	if (y > x)    //大数在前
	{
		t = x;
		x = y;
		y = t;
	}
	
	while (y != 0)
	{
		k = x%y;;
		x = y;
		y = k;
	}

	//lcm(a,b) = (a/gcd(a,b)) * b;