P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题

发布时间 2023-12-17 17:22:50作者: OKM_IS
首先最大公因数和最小公倍数之积等于两个原数的积,这是基本性质
然后两个数中,最小也是大于等于最大公因数,最大不超过最小公倍数
最暴力的方法是,在这个范围内遍历其中一个数,积除以这个数得到另一个数,然后用辗转相除法进行判断就可以求解。
当然,可以缩短范围。缩短范围有两个基本思想:
以下称满足条件的数分别为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.