hdu 4497 GCD and LCM(組合數學)

題目鏈接：hdu 4497 GCD and LCM

題目大意：給出三個數的最大公約數和最小公倍數，問說有多少種三個數滿足。

解題思路：首先用k=l/g，剩下的數即為三個中還需要存在的因子的乘積。然後將k分解成質因子；

以6 72為例，k = 72/6=12，k分解成質因子為2，2，3，不同因子間肯定是互相不影響的，只要計算出每種因子的放法，相乘即為總數。

現在考慮2這個因子，總共有兩個c=2.首先可以確定的是三個數中肯定有一個數包含因子為2^c，所以C(3,1)選中一個為該數；

然後剩下兩個位置，一個位置肯定不能含有該因子，否則會影響最大公約數的值，所以C(2,1)選中一個位置不能有該因子；

那麼最後剩下的一個位置就有1~c-1和0兩種可能；並且0是比較特殊的，只會有一種而不是兩種，如果這裡不單獨考慮，則在C(2,1)那步將重復計算兩個位置均為空的情況。

然後還有一個比較特殊的就是存在兩個位置為2^c，單獨考慮C(3,2)；

最後公示化簡為6*c。

<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PC9wPgo8cHJlIGNsYXNzPQ=="brush:java;">#include #include #include #include using namespace std; typedef long long ll; ll g, l; ll solve () { if (l%g) return 0; ll ans = 1; ll k = l / g; ll t = sqrt((double)k); for (ll i = 2; i <= t; i++) { if (k % i) continue; ll c = 0; while (k%i == 0) { c++; k /= i; } ans = ans * 6 * c; } if (k != 1) ans = ans * 6; return ans; } int main () { int cas; scanf("%d", &cas); while (cas--) { cin >> g >> l; cout << solve() << endl; } return 0; }