QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#551273#9248. An Easy Math Problemucup-team4435#AC ✓8ms3628kbC++208.9kb2024-09-07 16:14:362024-10-31 22:04:34

Judging History

你现在查看的是测评时间为 2024-10-31 22:04:34 的历史记录

  • [2024-10-31 22:38:30]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:8ms
  • 内存:3632kb
  • [2024-10-31 22:36:43]
  • hack成功,自动添加数据
  • (/hack/1098)
  • [2024-10-31 22:15:41]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:8ms
  • 内存:3688kb
  • [2024-10-31 22:13:58]
  • hack成功,自动添加数据
  • (/hack/1096)
  • [2024-10-31 22:04:34]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:8ms
  • 内存:3628kb
  • [2024-10-31 22:00:43]
  • hack成功,自动添加数据
  • (/hack/1095)
  • [2024-09-07 16:14:36]
  • 评测
  • 测评结果:100
  • 用时:8ms
  • 内存:3760kb
  • [2024-09-07 16:14:36]
  • 提交

answer

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

using ll = long long;
using ld = long double;

#define all(a) begin(a), end(a)
#define len(a) int((a).size())

/*
 * Don't forget to run dynamic_montgomery::set_mod method, before using it.
 * Mod must be prime.
 * Mod must be less than 2^62
*/

class dynamic_montgomery {
private:
    int64_t value;
    inline static uint64_t mod = 0;
    inline static uint64_t inv_neg_mod = 0;
    inline static uint64_t neg_mod = 0;

    static uint64_t reduce(const __uint128_t &value) {
        return (value + __uint128_t(uint64_t(value) * inv_neg_mod) * mod) >> 64;
    }

public:
    static void set_mod(uint64_t new_mod) {
        assert(new_mod <= uint64_t(1) << 62);
        mod = new_mod;

        inv_neg_mod = mod;
        for (int i = 0; i < 6; ++i) {
            inv_neg_mod *= uint64_t(2) - mod * inv_neg_mod;
        }
        inv_neg_mod *= -1;
        assert(mod * inv_neg_mod == uint64_t(-1));

        neg_mod = (-__uint128_t(mod)) % mod;
    }

    static uint64_t get_mod() {
        return mod;
    }

    dynamic_montgomery() : value(0) {}
    dynamic_montgomery(const dynamic_montgomery &x) : value(x.value) {}

    template<typename T, typename U = std::enable_if_t<std::is_integral<T>::value>>
    dynamic_montgomery(const T &x) : value(!x ? 0 : reduce(__uint128_t(x % int64_t(mod) + int64_t(mod)) * neg_mod)) {}

    uint64_t get() const {
        auto real_value = reduce(value);
        return real_value < mod ? real_value : real_value - mod;
    }

    template<typename T>
    dynamic_montgomery power(T degree) const {
        degree = (degree % int64_t(mod - 1) + int64_t(mod - 1)) % int64_t(mod - 1);
        dynamic_montgomery prod = 1, a = *this;
        for (; degree > 0; degree >>= 1, a *= a)
            if (degree & 1)
                prod *= a;

        return prod;
    }

    dynamic_montgomery inv() const {
        return power(-1);
    }

    dynamic_montgomery& operator=(const dynamic_montgomery &x) {
        value = x.value;
        return *this;
    }

    dynamic_montgomery& operator+=(const dynamic_montgomery &x) {
        if (int64_t(value += x.value - (mod << 1)) < 0) {
            value += mod << 1;
        }
        return *this;
    }

    dynamic_montgomery& operator-=(const dynamic_montgomery &x) {
        if (int64_t(value -= x.value) < 0) {
            value += mod << 1;
        }
        return *this;
    }

    dynamic_montgomery& operator*=(const dynamic_montgomery &x) {
        value = reduce(__uint128_t(value) * x.value);
        return *this;
    }

    dynamic_montgomery& operator/=(const dynamic_montgomery &x) {
        return *this *= x.inv();
    }

    friend dynamic_montgomery operator+(const dynamic_montgomery &x, const dynamic_montgomery &y) {
        return dynamic_montgomery(x) += y;
    }

    friend dynamic_montgomery operator-(const dynamic_montgomery &x, const dynamic_montgomery &y) {
        return dynamic_montgomery(x) -= y;
    }

    friend dynamic_montgomery operator*(const dynamic_montgomery &x, const dynamic_montgomery &y) {
        return dynamic_montgomery(x) *= y;
    }

    friend dynamic_montgomery operator/(const dynamic_montgomery &x, const dynamic_montgomery &y) {
        return dynamic_montgomery(x) /= y;
    }

    dynamic_montgomery operator-() const {
        return dynamic_montgomery(0) - *this;
    }

    bool operator==(const dynamic_montgomery &another) const {
        return value == another.value;
    }
};

using mint = dynamic_montgomery;

/*
 * Include dynamic_montgomery to use it.
*/

namespace factorizer {
    using ull = unsigned long long;

    bool is_prime(ull value) {
        if (value < 2)
            return false;

        for (ull x : {2, 3, 5, 7, 11}) {
            if (value == x)
                return true;

            if (value % x == 0)
                return false;
        }

        if (mint::get_mod() != value)
            mint::set_mod(value);

        ull d = value - 1;
        int s = __builtin_ctzll(d);
        d >>= s;

        const mint ONE = 1;
        const mint NEG_ONE = -1;

        auto miller_rabin = [&](ull base) {
            if (base == 0)
                return true;

            mint y = mint(base).power(d);
            if (y == ONE)
                return true;

            for (int i = 0; i < s; i++) {
                if (y == NEG_ONE)
                    return true;

                y *= y;
            }
            return false;
        };

        if (value < 4759123141ull) {
            for (ull base : {2, 7, 61})
                if (!miller_rabin(base % value))
                    return false;
        } else {
            for (ull base : {2, 325, 9375, 28178, 450775, 9780504, 1795265022})
                if (!miller_rabin(base % value))
                    return false;
        }
        return true;
    }

    // If there is no non-trivial divisor, returns value.
    ull find_any_nontrivial_divisor(ull value) {
        for (ull x : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29})
            if (value % x == 0)
                return x;

        if (is_prime(value) || value == 1)
            return value;

        if (mint::get_mod() != value)
            mint::set_mod(value);

        static std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
        const mint ONE = 1;
        while (true) {
            mint random_factor = rng() % (value - 1) + 1;

            auto f = [&](mint x) {
                return x * x + random_factor;
            };

            mint x = rng() % (value - 2) + 2;
            mint y = x;
            ull g = 1;
            while (g == 1) {
                mint prod = ONE;
                mint save_x = x;
                mint save_y = y;

                static constexpr int STEP = 128;
                for (int i = 0; i < STEP; i++) {
                    x = f(x);
                    y = f(f(y));
                    prod *= x - y;
                }

                g = std::gcd(prod.get(), value);
                if (g == 1)
                    continue;

                x = save_x;
                y = save_y;
                for (int i = 0; i < STEP; i++) {
                    x = f(x);
                    y = f(f(y));
                    g = std::gcd((x - y).get(), value);
                    if (g != 1)
                        break;
                }

                if (g != 1 && g != value)
                    return g;
            }
        }
    }

    // If n is divisible by p^d and not divisible by p^{d + 1} then p will occur d times.
    template<typename T>
    std::vector<T> get_all_prime_factors_with_duplicates(T value) {
        std::vector<T> res;

        auto dfs = [&](auto self, ull v) -> void {
            if (v == 1)
                return;

            ull x = find_any_nontrivial_divisor(v);
            if (x == v) {
                res.push_back(x);
                return;
            }
            self(self, x);
            self(self, v / x);
        };

        dfs(dfs, value);
        std::sort(res.begin(), res.end());
        return res;
    }

    // Return all prime factors in the format (prime, degree) sorted by prime.
    template<typename T>
    std::vector<std::pair<T, int>> get_all_prime_factors(T value) {
        auto prime_factors = get_all_prime_factors_with_duplicates(value);
        std::vector<std::pair<T, int>> factors;
        for (int i = 0, j = 0; i < int(prime_factors.size()); i = j) {
            while (j < int(prime_factors.size()) && prime_factors[i] == prime_factors[j])
                j++;

            factors.emplace_back(prime_factors[i], j - i);
        }
        return factors;
    }

    // Returns all factors of the number sorted in increasing order.
    template<typename T>
    std::vector<T> get_all_factors(T value) {
        std::vector<T> divs{1};
        for (auto [p, d] : get_all_prime_factors(value)) {
            int prev_size = divs.size();
            for (int i = 0; i < prev_size; i++) {
                T coeff = 1;
                for (int j = 0; j < d; j++) {
                    coeff *= p;
                    divs.push_back(divs[i] * coeff);
                }
            }
        }

        std::sort(divs.begin(), divs.end());
        return divs;
    }
} // namespace factorizer

using factorizer::is_prime;
using factorizer::get_all_prime_factors;
using factorizer::get_all_factors;

void solve(int /* test_num */) {
    ll n;
    cin >> n;
    ll ans = 1;
    for (auto [_, d] : get_all_prime_factors(n)) {
        ans *= 2 * d + 1;
    }
    cout << (ans + 1) / 2 << '\n';
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tests;
    cin >> tests;
    for (int test_num = 1; test_num <= tests; test_num++) {
        solve(test_num);
    }
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3628kb

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: 3620kb

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: 3596kb

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