codeforces1033D 2000分数学-白红宇

codeforces1033D 2000分数学

阅读量：294 次

发布时间：2019-03-03

本文共 3584 字，大约阅读时间需要 11 分钟。

为了求解问题，我们首先分析每个数a_i的质因数分解情况，然后将它们相乘得到sum，最后计算sum的约数个数。具体步骤如下：

分析每个a_i的质因数分解：

检查a_i是否为某个数的四次方、立方或平方。若不是，则判断其是否是两个不同质数的乘积。

根据判断结果，记录对应的质因数及其指数。

累加质因数指数：

对于每个质因数，将其在sum中的总指数累加。

计算约数个数：

将sum的质因数分解中的每个指数加1，相乘得到约数个数。

通过上述步骤，可以高效地计算出sum的约数个数，并对结果取模。

代码实现：

#include 
   
    
using namespace std;
const ll mod = 998244353;
const int maxn = 1e4 + 5;
const double eps = 1e-6;
int n;
int cnt = 0, cur = 0;
ll ans = 1;
struct node {
    ll x, num;
} a[MAXN];
struct prime {
    ll x, num;
} p[MAXN];
ll four(ll x) {
    ll y = pow(x, 1.0 / 4) + eps;
    if (y * y * y * y == x) {
        bool flag = 0;
        for (int i = 1; i <= cnt; i++) {
            if (y == p[i].x) {
                flag = 1;
                p[i].num += 4;
                break;
            }
        }
        if (!flag) {
            p[++cnt].x = y;
            p[cnt].num = 4;
        }
        return 1;
    }
    return 0;
}
ll three(ll x) {
    ll y = pow(x, 1.0 / 3) + eps;
    if (y * y * y == x) {
        bool flag = 0;
        for (int i = 1; i <= cnt; i++) {
            if (y == p[i].x) {
                flag = 1;
                p[i].num += 3;
                break;
            }
        }
        if (!flag) {
            p[++cnt].x = y;
            p[cnt].num = 3;
        }
        return 1;
    }
    return 0;
}
ll two(ll x) {
    ll y = pow(x, 1.0 / 2) + eps;
    if (y * y == x) {
        bool flag = 0;
        for (int i = 1; i <= cnt; i++) {
            if (y == p[i].x) {
                flag = 1;
                p[i].num += 2;
                break;
            }
        }
        if (!flag) {
            p[++cnt].x = y;
            p[cnt].num = 2;
        }
        return 1;
    }
    return 0;
}
void add_a(ll x, ll num) {
    bool flag = 0;
    for (int i = 1; i <= cur; i++) {
        if (x == a[i].x) {
            flag = 1;
            a[i].num += num;
            break;
        }
    }
    if (!flag) {
        a[++cur].x = x;
        a[cur].num = num;
    }
}
void add_p(ll x, ll num) {
    bool flag = 0;
    for (int i = 1; i <= cnt; i++) {
        if (x == p[i].x) {
            flag = 1;
            p[i].num += num;
            break;
        }
    }
    if (!flag) {
        p[++cnt].x = x;
        p[cnt].num += num;
    }
}
void try1(int i) {
    bool flag = 0;
    for (int j = i + 1; j <= cur; j++) {
        ll y = __gcd(a[i].x, a[j].x);
        if (y > 1) {
            flag = 1;
            add_p(y, a[i].num);
            add_p(a[i].x / y, a[i].num);
            break;
        }
    }
    if (!flag) {
        ans *= (a[i].num + 1);
        ans %= mod;
        ans *= (a[i].num + 1);
        ans %= mod;
    }
}
void solve() {
    for (int i = 1; i <= cur; i++) {
        bool flag = 0;
        for (int j = 1; j <= cnt; j++) {
            if (a[i].x % p[j].x == 0) {
                add_p(p[j].x, a[i].num);
                add_p(a[i].x / p[j].x, a[i].num);
                flag = 1;
                break;
            }
        }
        if (!flag) {
            try1(i);
        }
    }
}
void cal() {
    for (int i = 1; i <= cnt; i++) {
        ans *= (p[i].num + 1);
        ans %= mod;
    }
    printf("%lld\n", ans);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        ll x;
        scanf("%lld", &x);
        if (four(x) || three(x) || two(x)) {
            continue;
        } else {
            add_a(x, 1);
        }
    }
    solve();
    cal();
    return 0;
}