首先最大公因数和最小公倍数之积等于两个原数的积，这是基本性质 然后两个数中，最小也是大于等于最大公因数，最大不超过最小公倍数 最暴力的方法是，在这个范围内遍历其中一个数，积除以这个数得到另一个数，然后用辗转相除法进行判断就可以求解。 当然，可以缩短范围。缩短范围有两个基本思想： 以下称满足条件的数分别为p，以及q （一）：只有是最大公因数倍数，或者是最小公倍数约数的数的枚举才有意义，因此可以初始值为x，每次加x（枚举最大公因数的倍数），或者用y/i来枚举其约数，i初始时为1，y%i==0时才判断gcd。 （二）：显然，如果最大公因数是2，最小公倍数是60，那么两个数的积是120，满足这个条件的p，q是成对的，并且在sqrt（120）前后是对称的。因此枚举数的时候，结束条件可以是小于等于sqrt（120），然后在结束后将结果乘以2即可。但是这会出现一个问题，因为如果sqrt（xy）是一个整数，那么在枚举x=sqrt（xy）时求得的p=q，此答案并没有"成对"不该被乘以二，需要特判，或者开一个flag变量，在结尾时判断flag减去多加的1。 对于（一）中提出的性质，有一个更进一步的剪枝方法。如果用枚举最小公倍数的约数，我们实际上是得到y%i==0后，将y/i与xy/(y/i)=xi，这两个数进行gcd判断。那么同样以上面的最小公倍数为60举例，如果我们将i从1枚举到60，当我们得到y/i=60后，实际上，也已经得知了后面一定会枚举到y/i=1（i=60时），因为i和y/i都是y的约数。可以发现，其实对于i和y/i，其在sqrt（60）前后也是对称的，因此循环进行的条件可以为i小于根号y。 这个与上面的（二）的不同是，（二）中枚举一次p或者q，只进行一次gcd判断。而这个（一）的进一步剪枝，则每次枚举i（即枚举了q=y/i），要进行两次gcd判断，一次是以i为q，一次是以y/i为q。当然这里也要注意特判，如果会出现p=q，那就只能判断一次，不要加了两次ans。这种判断出来的结果不需要乘以2.
标签：NOIP2001,公倍数,最小,sqrt,60,枚举,P1029,公因数 From： https://www.cnblogs.com/OKM-IS/p/17909400.html