QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#611952#9309. GraphDE_aemmprtyAC ✓875ms15528kbC++172.1kb2024-10-05 00:37:142024-10-05 00:37:15

Judging History

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

  • [2024-10-05 00:37:15]
  • 评测
  • 测评结果:AC
  • 用时:875ms
  • 内存:15528kb
  • [2024-10-05 00:37:14]
  • 提交

answer

/*******************************
| Author:  DE_aemmprty
| Problem: Graph
| Contest: Virtual Judge - QOJ
| URL:     https://vjudge.net/problem/QOJ-9309
| When:    2024-10-05 00:02:28
| 
| Memory:  1014 MB
| Time:    3000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;

long long read() {
    char c = getchar();
    long long x = 0, p = 1;
    while ((c < '0' || c > '9') && c != '-') c = getchar();
    if (c == '-') p = -1, c = getchar();
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return x * p;
}

const int N = 1e6 + 7, Q = 1e6;
const long long mod = 998244353;

long long n, g[N * 2];
bool vis[N];
vector <long long> prime;

long long ksm(long long x, long long y) {
    long long res = 1; x %= mod;
    for (; y; y >>= 1, (x *= x) %= mod)
        if (y & 1)
            (res *= x) %= mod;
    return res;
}

long long getID(long long x) { return x <= Q ? x : Q + n / x;}

void calcG() {
    for (long long i = 1; prime[i] * prime[i] <= n; i ++)
        for (long long j = n; j >= prime[i] * prime[i]; j = n / (n / j + 1))
            g[getID(j)] -= g[getID(j / prime[i])] - g[prime[i - 1]];
}

long long f(long long x) {
    if (x == 1) return 1;
    if (x == 2) return 1;
    if (x == 3) return 3;
    long long num = g[getID(x)] - g[getID(x >> 1)] + 2;
    // printf("%d - %d's prime : %lld\n", x / 2 + 1, x, num - 2);
    return (x - num + 1) % mod * ksm(x, num - 2) % mod;
}

void solve() {
    n = read();
    prime.push_back(1);
    for (long long i = 2; i <= Q; i ++) {
        if (!vis[i]) {
            prime.push_back(i);
            for (long long j = i * i; j <= Q; j += i)
                g[j] = 1, vis[j] = 1;
        }
    }
    for (long long i = n; i > 1; i = n / (n / i + 1))
        g[getID(i)] = i - 1;
    calcG();
    long long ans = 1;
    long long l = 1;
    while (l <= n) {
        long long r = n / (n / l);
        (ans *= ksm(f(n / l), r - l + 1)) %= mod;
        l = r + 1;
    }
    cout << ans;
}

signed main() {
    int t = 1;
    while (t --) solve();
    return 0;
}

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

详细

Test #1:

score: 100
Accepted
time: 8ms
memory: 13752kb

input:

4

output:

8

result:

ok answer is '8'

Test #2:

score: 0
Accepted
time: 8ms
memory: 13996kb

input:

2

output:

1

result:

ok answer is '1'

Test #3:

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

input:

123

output:

671840470

result:

ok answer is '671840470'

Test #4:

score: 0
Accepted
time: 8ms
memory: 14412kb

input:

233

output:

353738465

result:

ok answer is '353738465'

Test #5:

score: 0
Accepted
time: 13ms
memory: 14264kb

input:

5981

output:

970246821

result:

ok answer is '970246821'

Test #6:

score: 0
Accepted
time: 8ms
memory: 13728kb

input:

86422

output:

897815688

result:

ok answer is '897815688'

Test #7:

score: 0
Accepted
time: 13ms
memory: 14220kb

input:

145444

output:

189843901

result:

ok answer is '189843901'

Test #8:

score: 0
Accepted
time: 13ms
memory: 14076kb

input:

901000

output:

819449452

result:

ok answer is '819449452'

Test #9:

score: 0
Accepted
time: 13ms
memory: 14832kb

input:

1000000

output:

113573943

result:

ok answer is '113573943'

Test #10:

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

input:

23333333

output:

949849384

result:

ok answer is '949849384'

Test #11:

score: 0
Accepted
time: 16ms
memory: 14184kb

input:

102850434

output:

604886751

result:

ok answer is '604886751'

Test #12:

score: 0
Accepted
time: 48ms
memory: 13344kb

input:

998244353

output:

0

result:

ok answer is '0'

Test #13:

score: 0
Accepted
time: 44ms
memory: 13064kb

input:

1000000007

output:

318420284

result:

ok answer is '318420284'

Test #14:

score: 0
Accepted
time: 72ms
memory: 13812kb

input:

2147483547

output:

688759898

result:

ok answer is '688759898'

Test #15:

score: 0
Accepted
time: 118ms
memory: 14256kb

input:

5120103302

output:

116870489

result:

ok answer is '116870489'

Test #16:

score: 0
Accepted
time: 290ms
memory: 13736kb

input:

19834593299

output:

523663743

result:

ok answer is '523663743'

Test #17:

score: 0
Accepted
time: 552ms
memory: 14868kb

input:

52500109238

output:

195086665

result:

ok answer is '195086665'

Test #18:

score: 0
Accepted
time: 778ms
memory: 13780kb

input:

84848352911

output:

107959260

result:

ok answer is '107959260'

Test #19:

score: 0
Accepted
time: 875ms
memory: 14040kb

input:

99824435322

output:

0

result:

ok answer is '0'

Test #20:

score: 0
Accepted
time: 872ms
memory: 15528kb

input:

99999999354

output:

316301711

result:

ok answer is '316301711'

Test #21:

score: 0
Accepted
time: 868ms
memory: 15380kb

input:

100000000000

output:

396843576

result:

ok answer is '396843576'

Extra Test:

score: 0
Extra Test Passed