QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#657749#9248. An Easy Math ProblemVegetog#WA 38ms3856kbC++203.9kb2024-10-19 15:23:482024-10-19 15:23:54

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-10-19 15:23:54]
  • Judged
  • Verdict: WA
  • Time: 38ms
  • Memory: 3856kb
  • [2024-10-19 15:23:48]
  • Submitted

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
using ll =long long;
const int N=2e5+6;

namespace prime_fac {
const int S = 8; // 随机算法判定次数,8~10 就够了

// 龟速乘
    long long mult_mod(long long a, long long b, long long c) {
        a %= c, b %= c;
        long long ret = 0;
        long long tmp = a;
        while (b) {
            if (b & 1) {
                ret += tmp;
                if (ret > c) ret -= c;
            }
            tmp <<= 1;
            if (tmp > c) tmp -= c;
            b >>= 1;
        }
        return ret;
    }

    // 快速幂
    long long qow_mod(long long a, long long n, long long _mod) {
        long long ret = 1;
        long long temp = a % _mod;
        while (n) {
            if (n & 1) ret = mult_mod(ret, temp, _mod);
            temp = mult_mod(temp, temp, _mod);
            n >>= 1;
        }
        return ret;
    }

    // 是合数返回true,不一定是合数返回false
    bool check(long long a, long long n, long long x, long long t) {
        long long ret = qow_mod(a, x, n);
        long long last = ret;
        for (int i = 1; i <= t; i++) {
            ret = mult_mod(ret, ret, n);
            if (ret == 1 && last != 1 && last != n - 1) return true;
            last = ret;
        }
        if (ret != 1) return true;
        return false;
    }

    // 是素数返回true,不是返回false
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    bool Miller_Rabin(long long n) {
        if (n < 2) return false;
        if (n == 2) return true;
        if ((n & 1) == 0) return false;
        long long x = n - 1;
        long long t = 0;
        while ((x & 1) == 0) { x >>= 1; t++; }

        for (int i = 0; i < S; i++) {
            long long a = rng() % (n - 1) + 1;
            if (check(a, n, x, t))
                return false;
        }

        return true;
    }

    long long factor[100];// 存质因数
    int tol; // 质因数的个数,0~tol-1

    long long gcd(long long a, long long b) {
        long long t;
        while (b) {
            t = a;
            a = b;
            b = t % b;
        }
        if (a >= 0) return a;
        return -a;
    }

    long long pollard_rho(long long x, long long c) {
        long long i = 1, k = 2;
        long long x0 = rng() % (x - 1) + 1;
        long long y = x0;
        while (1) {
            i++;
            x0 = (mult_mod(x0, x0, x) + c) % x;
            long long d = gcd(y - x0, x);
            if (d != 1 && d != x) return d;
            if (y == x0) return x;
            if (i == k) { y = x0; k += k; }
        }
    }
    // 对n质因数分解,存入factor,k一般设置为107左右
    void findfac(long long n, int k) {
        if (n == 1) return;
        if (Miller_Rabin(n)) {
            factor[tol++] = n;
            return;
        }
        long long p = n;
        int c = k;
        while (p >= n) p = pollard_rho(p, c--);
        findfac(p, k);
        findfac(n / p, k);
    }
    vector<int> fac(long long n) {
        tol = 0;
        vector<int>ret;
        findfac(n, 107);
        for (int i = 0; i < tol; i++)ret.push_back(factor[i]);
        return ret;
    }
}

void solve()
{
    ll n,m=0,x;
    cin>>n;
    vector<int> fac = prime_fac::fac(n);
    vector<ll> a;
    unordered_map<ll, ll> mp;
    for(auto i : fac) {
        if(mp[i] == 0) 
            a.push_back(i);
        mp[i] ++ ;
    } 
    ll ans = 1, res = 0;
    for(auto i : a) {
        ans *= mp[i] * 2;
    }
    if(a.size() > 1) {
        for(auto i : a) {
            res += mp[i] * 2;
        }
    }
    ans = (ans + res) / 2;
    cout << ans + 1 << "\n";
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr),cout.tie(nullptr);

    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
}

详细

Test #1:

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

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: 38ms
memory: 3592kb

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:

523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
523
...

result:

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