QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#611952 | #9309. Graph | DE_aemmprty | AC ✓ | 875ms | 15528kb | C++17 | 2.1kb | 2024-10-05 00:37:14 | 2024-10-05 00:37:15 |
Judging History
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