題目描述

Hanks 博士是 BT (Bio-Tech，生物技術(shù)) 領(lǐng)域的知名專家，他的兒子名叫 Hankson。現(xiàn)

在，剛剛放學(xué)回家的 Hankson 正在思考一個(gè)有趣的問(wèn)題。

今天在課堂上，老師講解了如何求兩個(gè)正整數(shù) c1 和 c2 的最大公約數(shù)和最小公倍數(shù)。現(xiàn)

在 Hankson 認(rèn)為自己已經(jīng)熟練地掌握了這些知識(shí)，他開(kāi)始思考一個(gè)“求公約數(shù)”和“求公

倍數(shù)”之類(lèi)問(wèn)題的“逆問(wèn)題”，這個(gè)問(wèn)題是這樣的：已知正整數(shù) a0,a1,b0,b1，設(shè)某未知正整

數(shù) x 滿足：

1． x 和 a0 的最大公約數(shù)是 a1；

2． x 和 b0 的最小公倍數(shù)是 b1。

Hankson 的“逆問(wèn)題”就是求出滿足條件的正整數(shù) x。但稍加思索之后，他發(fā)現(xiàn)這樣的

x 并不唯一，甚至可能不存在。因此他轉(zhuǎn)而開(kāi)始考慮如何求解滿足條件的 x 的個(gè)數(shù)。請(qǐng)你幫

助他編程求解這個(gè)問(wèn)題。

輸入輸出格式

輸入格式：

第一行為一個(gè)正整數(shù) n，表示有 n 組輸入數(shù)據(jù)。接下來(lái)的 n 行每

行一組輸入數(shù)據(jù)，為四個(gè)正整數(shù) a0，a1，b0，b1，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開(kāi)。輸入

數(shù)據(jù)保證 a0 能被 a1 整除，b1 能被 b0 整除。

輸出格式：

輸出文件 son.out 共 n 行。每組輸入數(shù)據(jù)的輸出結(jié)果占一行，為一個(gè)整數(shù)。

對(duì)于每組數(shù)據(jù)：若不存在這樣的 x，請(qǐng)輸出 0；

若存在這樣的 x，請(qǐng)輸出滿足條件的 x 的個(gè)數(shù)；

輸入輸出樣例

輸入樣例#1： 2 41 1 96 288 95 1 37 1776 輸出樣例#1： 6 2

說(shuō)明

【說(shuō)明】

第一組輸入數(shù)據(jù)，x 可以是 9、18、36、72、144、288，共有 6 個(gè)。

第二組輸入數(shù)據(jù)，x 可以是 48、1776，共有 2 個(gè)。

【數(shù)據(jù)范圍】

對(duì)于 50%的數(shù)據(jù)，保證有 1≤a0，a1，b0，b1≤10000 且 n≤100。

對(duì)于 100%的數(shù)據(jù)，保證有 1≤a0，a1，b0，b1≤2,000,000,000 且 n≤2000。

NOip 2009 提高組 第二題

第一次自己證明出數(shù)論類(lèi)問(wèn)題…雞凍>w<，雖然效率爆炸…不過(guò)..不過(guò)，就是雞凍辣！！！

【思路】 ∵gcd(a,b)?lcm(a,b)=a?b$∵gcd(a,b)*lcm(a,b)=a*b$ 由題意得：lcm(x,b0)=b1$由題意得：lcm(x,b0)=b1$ ∴x?b0=b1?gcd(x,b0)$∴x*b0 = b1*gcd(x,b0)$ x$x$=b1b0$/frac{b1}{b0}$?$*$gcd(x,b0)$gcd(x,b0)$ 不妨設(shè)gcd(x,b0)=m$不妨設(shè)gcd(x,b0)=m$ 則有{x=b1b0?m①gcd(x,b0)=m②$則有/begin {cases} x=/frac{b1}{b0}*m ①///gcd(x,b0)=m ②/end {cases}$ 由②：xm與b0m互質(zhì)$由②：/frac{x}{m}與/frac{b0}{m}互質(zhì)$ 結(jié)合①有：b1b0與b0m互質(zhì)$結(jié)合①有：/frac{b1}{b0}與/frac{b0}{m}互質(zhì)$ 考慮到：b0m=b1x$考慮到：/frac{b0}{m}=/frac{b1}{x}$ ∴b1b0與b1x互質(zhì)$∴/frac{b1}{b0}與/frac{b1}{x}互質(zhì)$ ∴gcd(b1b0,b1x)=1Δ$∴gcd(/frac{b1}{b0},/frac{b1}{x})=1/Delta$ 此時(shí)考慮第一個(gè)條件gcd(x,a0)=a1$此時(shí)考慮第一個(gè)條件gcd(x,a0)=a1$ 易證gcd(a0a1,xa1)=1Δ$易證gcd(/frac{a0}{a1},/frac{x}{a1})=1/Delta$

上述兩個(gè)標(biāo)了三角形的條件即是我們的結(jié)論$上述兩個(gè)標(biāo)了三角形的條件即是我們的結(jié)論$ 為了考慮枚舉時(shí)的剪枝，可以結(jié)合整除性$為了考慮枚舉時(shí)的剪枝，可以結(jié)合整除性$ ∵lcm(x,b0)=b1$∵lcm(x,b0)=b1$ ∴x|b1$∴x|b1$ ∵gcd(x,a0)=a1$∵gcd(x,a0)=a1$ ∴a1|a0且a1|x$∴a1|a0且a1|x$

所以只要考慮即是b1的因數(shù)又是a1的倍數(shù)的x即可$所以只要考慮即是b1的因數(shù)又是a1的倍數(shù)的x即可$ 同時(shí)還有一個(gè)小技巧，我們可以只去枚舉1至b1??√的i，同時(shí)考慮b1/i就能縮小枚舉范圍$同時(shí)還有一個(gè)小技巧，我們可以只去枚舉1至/sqrt{b1}的i，同時(shí)考慮b1/i 就能縮小枚舉范圍$

hhhhhhhhhhhhh

—————————————我是萌萌的分割線————————————–