求助,第十三个测试点WA

P1593 因子和

tyiii @ 2024-03-29 11:40:38

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

struct {
    int prime, cnt;
}p[25];
int a, b, ans, siz, sum[25];
const int mod = 9901;
bitset<7072>che;
int prime[908], top;

void euler() {
    for (int i = 2; i <= 7071; ++i) {
        if (!che.test(i)) {
            prime[++top] = i;
        }
        for (int j = 1; j <= top && prime[j] * i <= 7071; ++j) {
            che.set(prime[j] * i);
            if (i % prime[j] == 0) break;
        }
    }
}

int ModExpFast(int a, int n, int m) {//快速幂取模
    int res = 1;
    a = a % m;
    while (n) {
        if ((n & 1) == 1)
            res = (res * a) % m;
        a = (a * a) % m;
        n = n >> 1;
    }
    return res;
}

int main() {
    cin >> a >> b;
    euler();
    for (int i = 1; i <= top; ++i) {
        if (a % prime[i] == 0) p[++siz].prime = prime[i];
        while (a % prime[i] == 0) {
            p[siz].cnt += b;
            a /= prime[i];
        }
    }
    if (a != 1) {
        p[++siz].prime = a;
        p[siz].cnt = 1;
    }//生成质因子表
    for (int i = 1; i <= siz; ++i) {
        int pr = p[i].prime, n = p[i].cnt;
        if ((pr - 1) % mod == 0) {
            sum[i] = 1 + n;
        }
        else {
            sum[i] = (((ModExpFast(pr, n + 1, mod) - 1 + mod) % mod) * ModExpFast(pr - 1, mod - 2, mod)) % mod;
        }
    }
    ans = 1;
    for (int i = 1; i <= siz; ++i) {
        ans = (ans * sum[i]) % mod;
    }
    cout << ans;
    return 0;
}

|