noip2001pj T2 最小公倍数和最大公约数问题
KingSann
输入二个正整数x0,y0(2≤x0≤100000,2≤y0≤1000000),求出满足下列条件的P,Q的个数.
条件:1.P,Q是正整数
2.要求P,Q以xO为最大公约数,以yO为最小公倍数.
试求,满足条件的所有可能的两个正整数的个数.
看完之后第一眼暴力,然后发现暴力貌似O(n^2)会炸,然后开始分析如何解决..
首先,众所周知lcm(a,b)=a*b/gcd(a,b),那么我们就可以把P,Q表示出来了.
P>=x
Q>=x
gcd(P,Q)=x
lcm(P,Q)=y
那么我们看一下以后一个式子,将gcd带进去.
lcm(P,Q)=P*Q/