题解 | #X-factor Chains#

【X-factor Chains】

题目需要让序列$aa$​​尽可能的长，且$a_i\mathrm{\mid }{a}_{i+1}a\_i|a\_\{i+1\}$，即$a_i\times t=a_{i+1}a\_i\backslash times\; t\; =\; a\_\{i+1\}$只要让$tt$尽可能小就行了，也就是$tt$是一个质数。

对$xx$​分解质因数得$x=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\mathrm{.}\mathrm{.}\mathrm{.}{p}_k^{{\alpha }_k}x=p\_1^\{\backslash alpha\_1\}p\_2^\{\backslash alpha\_2\}...p\_k^\{\backslash alpha\_k\}$​，即$a_{i+1}=a_i\times p_{j}a\_\{i+1\}=a\_i\backslash times\; p\_j$​，只需要将质因数$p_{j}p\_j$​​排列组合就行了。

可以注意到质因数的全排列是一个多重组合数，$S=\frac{(\sum {\alpha }_i)!}{\prod ({\alpha }_i!)}S=\backslash frac\{(\backslash sum\; \backslash alpha\_i)!\}\{\backslash prod\; (\backslash alpha\_i!)\}$。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 3e4 + 10;

int T, fac[N];
int x, total, sum, res;

void init() {
    fac[0] = 1;
    for (int i = 1; i <= 100; i++) fac[i] = fac[i - 1] * i;
}

signed main() {
    init();
    cin >> T;
    while (T--) {
        cin >> x;
        sum = total = 0;
        int tmp = x;
        int w = 1;
        for (int i = 2; i * i <= x; i++) {
            int cnt = 0;
            while (tmp % i == 0) {
                tmp /= i;
                cnt++;
            }
            if (cnt) {
                sum += cnt;
                w *= fac[cnt];
            }
        }
        if (tmp > 1) sum++;
        res = fac[sum] / w;

        cout << sum << " " << res << endl;
    }

    return 0;
}