QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#584411#9309. GraphqianyueWA 16ms14612kbC++202.2kb2024-09-23 13:57:262024-09-23 13:57:26

Judging History

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

  • [2024-09-23 13:57:26]
  • 评测
  • 测评结果:WA
  • 用时:16ms
  • 内存:14612kb
  • [2024-09-23 13:57:26]
  • 提交

answer

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

constexpr int mod = 998244353;

inline int add(int x, int y) {
    return (x + y >= mod ? x + y - mod : x + y);
}
inline int mul(int x, int y) {
    return 1ll * x * y % mod;
}
int qpow(int x, long long n) {
    int y = 1;
    for (; n; n /= 2, x = mul(x, x)) if (n & 1) y = mul(y, x);
    return y;
}

namespace Min25 {
constexpr int maxs = 1000000;
int pri[maxs / 7], lpf[maxs + 1], spri[maxs + 1], pcnt;
const int inv2 = qpow(2, mod - 2);

void sieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (!lpf[i]) {
            lpf[i] = ++pcnt;
            pri[lpf[i]] = i;
            spri[pcnt] = add(spri[pcnt], 1);
        }
        for (int j = 1, v; j <= lpf[i] && (v = i * pri[j]) <= n; j++) lpf[v] = j; 
    }
}
long long global_n;
int lim;
int le[maxs + 1], ge[maxs + 1];
#define idx(v) (v <= lim ? le[v] : ge[global_n / v])

long long G[maxs + 1];
long long lis[maxs + 1];
int cnt;

void initG(int n) {
    for (long long i = 1, j, v; i <= n; i = n / j + 1) {
        j = n / i;
        v = j % mod;
        lis[++cnt] = j;
        (j <= lim ? le[j] : ge[global_n / j]) = cnt;
        G[cnt] = v - 1;
    }
}
void calcFprime() {
    for (int k = 1; k <= pcnt; k++) {
        int p = pri[k];
        long long sqrp = 1ll * p * p;
        for (int i = 1; lis[i] >= sqrp; i++) {
            long long v = lis[i] / p;
            int id = idx(v);
            G[i] -= G[id] - (k - 1);
        }
    }
}
void init(long long n) {
    global_n = n;
    lim = sqrt(n);
    sieve(lim + 1000);
    initG(n);
    calcFprime();
}
int get(long long n) {
    return G[idx(n)];
}
}
using Min25::get;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n;
    cin >> n;

    Min25::init(n);

    int res = 1;
    for (long long l = 1, r; l <= n; l = r + 1) {
        r = n / (n / l);
        int m = n / l;
        int cnt = get(m) - get(m / 2);
        int k = 1 + cnt + (m - cnt - 1 > 0);
        int ans = qpow(m % mod, k - 2);
        if (m - cnt - 1 > 0) {
            ans = mul(ans, (m - cnt - 1) % mod);
        }
        res = mul(res, qpow(ans, r - l + 1));
    }
    cout << res;


    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 11840kb

input:

4

output:

8

result:

ok answer is '8'

Test #2:

score: 0
Accepted
time: 0ms
memory: 11840kb

input:

2

output:

1

result:

ok answer is '1'

Test #3:

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

input:

123

output:

671840470

result:

ok answer is '671840470'

Test #4:

score: 0
Accepted
time: 0ms
memory: 13884kb

input:

233

output:

353738465

result:

ok answer is '353738465'

Test #5:

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

input:

5981

output:

970246821

result:

ok answer is '970246821'

Test #6:

score: 0
Accepted
time: 0ms
memory: 13868kb

input:

86422

output:

897815688

result:

ok answer is '897815688'

Test #7:

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

input:

145444

output:

189843901

result:

ok answer is '189843901'

Test #8:

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

input:

901000

output:

819449452

result:

ok answer is '819449452'

Test #9:

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

input:

1000000

output:

113573943

result:

ok answer is '113573943'

Test #10:

score: 0
Accepted
time: 3ms
memory: 11932kb

input:

23333333

output:

949849384

result:

ok answer is '949849384'

Test #11:

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

input:

102850434

output:

604886751

result:

ok answer is '604886751'

Test #12:

score: 0
Accepted
time: 12ms
memory: 14492kb

input:

998244353

output:

0

result:

ok answer is '0'

Test #13:

score: -100
Wrong Answer
time: 16ms
memory: 14612kb

input:

1000000007

output:

349542984

result:

wrong answer expected '318420284', found '349542984'