QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#806163#9248. An Easy Math ProblemKKT89AC ✓8ms3792kbC++234.3kb2024-12-08 22:28:432024-12-08 22:28:43

Judging History

你现在查看的是最新测评结果

  • [2024-12-08 22:28:43]
  • 评测
  • 测评结果:AC
  • 用时:8ms
  • 内存:3792kb
  • [2024-12-08 22:28:43]
  • 提交

answer

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) { return (ull)rng() % B; }

// verify:https://www.acmicpc.net/problem/4149
namespace factorize {
using u64 = uint64_t;
using u128 = __uint128_t;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

u64 binary_gcd(u64 a, u64 b) {
    if (a == 0) return b;
    if (b == 0) return a;
    const int n = __builtin_ctzll(a | b);
    a >>= __builtin_ctzll(a);
    while (b > 0) {
        b >>= __builtin_ctzll(b);
        if (a > b) std::swap(a, b);
        b -= a;
    }
    return a << n;
}

u128 pow(u128 a, u64 n, u128 mod) {
    u128 res = 1;
    if (a >= mod) a %= mod;
    while (n > 0) {
        if (n & 1) {
            res *= a;
            if (res >= mod) res %= mod;
        }
        a *= a;
        if (a >= mod) a %= mod;
        n >>= 1;
    }
    return res;
}

bool miller_rabin(u64 n, vector<u64> v) {
    u64 d = n - 1;
    while (~d & 1)
        d >>= 1;
    for (u64 a : v) {
        if (n <= a) break;
        u64 t = d;
        u128 y = pow(a, t, n);
        while (t != n - 1 and y != 1 and y != n - 1) {
            y *= y;
            if (y >= n) y %= n;
            t *= 2;
        }
        if (y != n - 1 and t % 2 == 0) return false;
    }
    return true;
}

bool is_prime(u64 n) {
    if (n <= 1) return false;
    if (~n & 1) return (n == 2);
    if (n < (1LL << 30)) {
        return miller_rabin(n, {2, 7, 61});
    } else {
        return miller_rabin(n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});
    }
}

template <typename T> T pollard_rho(T n) {
    if (~n & 1) return 2;
    if (is_prime(n)) return n;

    static u128 x, y, c, d;
    auto f = [&](u128 x) { return (x * x % n + c) % n; };
    auto rnd_ = [&](T l, T r) { return rng() % (r - l + 1) + l; };

    x = rnd_(2, n);
    y = x;
    c = rnd_(1, n);
    d = 1;

    while (d == 1) {
        x = f(x);
        y = f(y);
        y = f(y);
        d = binary_gcd((x > y ? x - y : y - x), n);
        if ((T)d == n) {
            return pollard_rho(n);
        }
    }
    if (is_prime(d)) {
        return d;
    } else {
        return pollard_rho(d);
    }
}

template <typename T> vector<T> prime_factor(T n) {
    vector<T> res;
    for (T i = 2; i * i <= n;) {
        while (n % i == 0) {
            n /= i;
            res.emplace_back(i);
        }
        i += 1 + (~n & 1);
        if (i >= 101 and n >= (1 << 20)) {
            while (n > 1) {
                auto p = pollard_rho(n);
                while (n % p == 0) {
                    n /= p;
                    res.emplace_back(p);
                }
            }
            break;
        }
    }
    if (n > 1) res.emplace_back(n);
    sort(res.begin(), res.end());
    return res;
}

template <typename T> map<T, int> factor_count(T n) {
    map<T, int> mp;
    for (auto &x : prime_factor(n))
        mp[x]++;
    return mp;
}

template <typename T> vector<T> divisors(T n) {
    if (n == 0) return {};
    vector<pair<T, int>> v;
    for (auto &p : factor_count(n))
        v.push_back(p);
    vector<T> res;
    auto f = [&](auto self, int i, T x) -> void {
        if (i == (int)v.size()) {
            res.push_back(x);
            return;
        }
        for (int j = 0; j <= v[i].second; ++j) {
            self(self, i + 1, x);
            if (j + 1 <= v[i].second) {
                x *= v[i].first;
            }
        }
    };
    f(f, 0, 1);
    sort(res.begin(), res.end());
    return res;
}

} // namespace factorize

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int q;
    cin >> q;
    while (q--) {
        ll n;
        cin >> n;
        auto f = factorize::factor_count(n);
        ll res = 1;
        vector<ll> v;
        for (auto p : f) {
            v.push_back(p.second);
        }
        int m = v.size();
        for (int i = 0; i < m; ++i) {
            ll u = v[i];
            for (int j = i + 1; j < m; ++j) {
                u *= (2LL * v[j] + 1);
            }
            res += u;
        }
        cout << res << "\n";
    }
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3632kb

input:

10
1
2
3
4
5
6
7
8
9
10

output:

1
2
2
3
2
5
2
4
3
5

result:

ok 10 lines

Test #2:

score: 0
Accepted
time: 2ms
memory: 3792kb

input:

2000
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
6469693230
646969323...

output:

29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
29525
...

result:

ok 2000 lines

Test #3:

score: 0
Accepted
time: 8ms
memory: 3620kb

input:

2000
1763047095
79735483
1016286871
2864801397
2327774116
2668010360
3469893354
3634459021
1613699068
781737219
574741575
2763134701
1458502604
1822260248
2281150332
2924219311
2493931196
3735904708
158802001
2006921221
729928782
1974841034
727412600
2873393292
1291087179
2741607663
1893408215
29827...

output:

14
5
2
5
23
95
68
14
8
68
203
14
23
32
38
41
8
8
14
2
608
41
158
338
23
41
14
5
14
41
14
203
41
14
17
446
5
53
59
878
2
14
365
203
14
203
2
122
32
95
41
41
5
23
14
41
5
5
14
122
23
203
608
23
41
122
2
14
95
2
68
41
203
14
230
41
68
23
50
14
32
14
8
5
5
5
68
68
122
293
473
5
41
41
14
2
14
14
5
2
122
...

result:

ok 2000 lines

Extra Test:

score: 0
Extra Test Passed