QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#576521#9248. An Easy Math Problemrxzfn639WA 3ms3884kbC++232.7kb2024-09-19 20:48:112024-09-19 20:48:11

Judging History

This is the latest submission verdict.

  • [2024-10-31 22:36:43]
  • hack成功,自动添加数据
  • (/hack/1098)
  • [2024-10-31 22:13:58]
  • hack成功,自动添加数据
  • (/hack/1096)
  • [2024-10-31 22:00:43]
  • hack成功,自动添加数据
  • (/hack/1095)
  • [2024-09-19 20:48:11]
  • Judged
  • Verdict: WA
  • Time: 3ms
  • Memory: 3884kb
  • [2024-09-19 20:48:11]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 P = 998244353;
i64 mul(i64 a, i64 b, i64 m) {
    return static_cast<__int128>(a) * b % m;
}
i64 power(i64 a, i64 b, i64 m) {
    i64 res = 1 % m;
    for (; b; b >>= 1, a = mul(a, a, m))
        if (b & 1)
            res = mul(res, a, m);
    return res;
}
bool isprime(i64 n) { // Miller-Rabin
    if (n < 2) return false;
    static constexpr int B[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
    for (int p : B) {
        if (n == p) return true;
        if (n % p == 0) return false;
    }
    i64 m = (n - 1) >> __builtin_ctz(n - 1);
    for (int p : B) {
        i64 t = m, a = power(p, m, n);
        while (t != n - 1 && a != 1 && a != n - 1) {
            a = mul(a, a, n);
            t *= 2;
        } 
        if (a != n - 1 && t % 2 == 0) return false;
    }
    return true;
}
vector<i64> factorize(i64 n) { // Pollard-Rho
    vector<i64> p;
    function<void(i64)> f = [&](i64 n) {
        if (n <= 10000) {
            for (int i = 2; i * i <= n; i++) 
                for ( ; n % i == 0; n /= i)
                    p.push_back(i);
            if (n > 1) 
                p.push_back(n);
            return;
        }
        if (isprime(n)) {
            p.push_back(n);
            return;
        }
        auto g = [&](i64 x) {
            return (mul(x, x, n) + 1) % n;
        };
        i64 x0 = 2;
        while (true) {
            i64 x = x0, y = x0;
            i64 d = 1, pow = 1, lam = 0, v = 1;
            while (d == 1) {
                y = g(y);
                ++lam;
                v = mul(v, abs(x - y), n);
                if (lam % 127 == 0) {
                    d = gcd(v, n);
                    v = 1;
                }
                if (pow == lam) {
                    x = y;
                    pow *= 2;
                    lam = 0;
                    d = gcd(v, n);
                    v = 1;
                }
            }
            if (d != n) {
                f(d);
                f(n / d);
                return;
            }
            ++x0;
        }
    };
    f(n);
    sort(p.begin(), p.end());
    return p;
}
void solve() {
    i64 n;
    cin >> n;
    auto p = factorize(n);
    int cnt = 0, ans = 1, siz = 0;
    for (int i = 0; i < p.size(); i++) {
        cnt++;
        if (i == p.size() || p[i] != p[i + 1]) {
            siz++;
            ans *= (cnt + 1);
            cnt = 0;
        }
    }
    if (siz > 1) ans++;
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    int t = 1; 
    cin >> t;
    while(t--) solve();
    return 0;
}

詳細信息

Test #1:

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

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: -100
Wrong Answer
time: 3ms
memory: 3884kb

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:

1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
1025
...

result:

wrong answer 1st lines differ - expected: '29525', found: '1025'