[noip2001普及(初中)組] 第二題《最大公約數和最小公倍數問題》解題報告

NO IMAGE

輸入二個正整數x0,y0(2<=x0<100000,2<=y0<=1000000),求出滿足下列條件的P,Q的個數

條件:  1.P,Q是正整數

2.要求P,Q以x0為最大公約數,以y0為最小公倍數.

試求:滿足條件的所有可能的兩個正整數的個數.

二個正整數x0,y0

滿足條件的所有可能的兩個正整數的個數

3 60

4

看這篇部落格的分析http://zhurui250.blog.163.com/blog/static/137270520201162414616998/

貼上過來

【分析】
gcd(a,b)為數a與數b的最大公約數(Greatest Common Divisor),lcm(a,b)為數a與數b的最小公倍數(least common multiple)。

題目給出了gcd(p,q)和lcm(p,q),讓我們求解p,q的正整數解數。
設s=lcm(p,q)/gcd(p,q),問題化為求解 xy=s 且 gcd(x,y)=1 的正整數解數。

——————————————–補充———————————————-

因為

設gcd(p,q) = G lcm(p, q) = L

根據lcm性質 p*q/G = L 且 p|G q|G (整除) 

則兩邊同時除G

p/G * q/G = L / G = s,由gcd性質可知 p/G與q/G互質

則原問題就變為了x*y=s 並且gcd(x, y)=1

————————————————————————————————–

因式分解就可以得到。

然後列舉s的因數x,得到另一個因數y,判斷gcd(x.y)是否等於1即可。詳見程式1

這裡講一個更有數學味的演算法,希望大家看完。

按照上面的分析,無非就是把問題轉化成為了求S的因數集合中,兩兩互質的數對的個數。
設 s=a[1]^p[1]*a[2]^p[2]*a[3]^p[3]……*a[n]^p[n]
設 x是s的一個因數,相對的因數是y=s/x

一定不存在a[i](s的質因數),a[i]|x且a[i]|y
於是,如果 a[i]|x,因為s=xy,所以 a[i]^p[i]|x 且,不存在a[i]|y  (符號打不出來,這裡表示不同餘)
設 b[i]=a[i]^p[i]
s總共有n個質因數,那麼答案一定是 2^n

這裡用語言簡單說明一下,通過剛才的證明,有xy=s,所以 x 必為 b陣列中若干不相同元素的乘積,那麼不是x因數的 b陣列中的元素,一定是y的因數,那麼考慮會選擇哪幾個元素相乘得到x,必然用二進位制加以列舉。
 
也就是說 s 有 n 中質因數,則一定有 2^n 種答案。