HDU4497 GCD and LCM（数论，质因子分解）

HDU4497 GCD and LCM

如果 \(G \% L != 0\) ，那么输出 \(0\) 。

否则我们有 \(L/G=(p_1^{r_1})\cdot(p_2^{r_2})\cdot(p_3^{r_3})\cdots(p_m^{r_m})\) 。

我们又有：

\[x=(p_1^{i_1})\cdot(p_2^{i_2})\cdot(p_3^{i_3})\cdots(p_m^{i_m}) \\ y=(p_1^{j_1})\cdot(p_2^{j_2})\cdot(p_3^{j_3})\cdots(p_m^{j_m}) \\ z=(p_1^{k_1})\cdot(p_2^{k_2})\cdot(p_3^{k_3})\cdots(p_m^{k_m}) \]

对于某个 \(r\) ，\(i、j、k\) 里面一定有一个是 \(r\) ，并且一定有一个是 \(0\) ，所以 \(i,j,k\) 有一下 \(3\) 种情况：

\((r\ 0\ 0)\) ，有 \(C(3,1)\) 种。
\((r\ 0\ r)\) ，有 \(C(3,1)\) 种。
\(r\ 0\ 1~r-1)\) ，有 \((r-1)\cdot A(3,3)\) 种。

所以一共是 \(6\times r\) 种。

时间复杂度为 \(O(\sqrt{n}\cdot \log n)\) 。

#include

using namespace std;

int t;
long long l ,g, ans;

int main()
{
    for(scanf("%d", &t); t--; ){
        scanf("%lld%lld", &l, &g);
        if(g % l == 0){
            long long tmp = g / l;
            ans = 1;
            for(int i = 2; i * i <= g / l; i++){
                long long r = 0;
                while(tmp % i == 0) r++, tmp /= i;
                if(r) ans *= (6 * r);
            }
            if(tmp != 1) ans *= 6;
            cout << ans << endl;
        }
        else{
            puts("0");
        }
    }
    return 0;
}