QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#572829 | #9309. Graph | 000226 | WA | 40ms | 16748kb | C++17 | 2.4kb | 2024-09-18 16:31:41 | 2024-09-18 16:31:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define lep(i, l, r) for(int i = (l); i <= (r); i ++)
#define rep(i, l, r) for(int i = (l); i >= (r); i --)
#define Lep(i, l, r) for(int i = (l); i < (r); i ++)
#define debug(...) fprintf (stderr, __VA_ARGS__)
//#define int long long
using i64 = long long;
using ld = long double;
using ui64 = unsigned long long;
const int P = 998244353;
inline int mod(int x) { return x + (x >> 31 & P); }
inline void pls(int &x, int y) { x = mod(x + y - P); }
inline void sub(int &x, int y) { x = mod(x - y); }
inline int add(int x, int y) { return mod (x + y - P); }
inline int dec(int x, int y) { return mod (x - y); }
inline int power(int x, i64 k) {
int res = 1;
while(k) {
if (k & 1) res = 1ll * res * x % P;
x = 1ll * x * x % P; k >>= 1;
} return res;
}
namespace Min25 {
#define LL long long
LL n;
const int N = 1e6 + 10;
int vis[N], p[N], tot;
void init(int n = 1e6) {
for(int i = 2; i <= n; i ++) {
if(! vis[i]) p[++ tot] = i;
for(int j = 1; p[j] * i <= n && j <= tot; j ++) {
vis[i * p[j]] = 1;
if(i % p[j] == 0) break;
}
}
}
int id0[N], id1[N];
LL val[N];
int num, sqr;
LL g[N];
inline int pos(LL x) {
if(x <= sqr) return id0[x];
else return id1[n / x];
}
i64 qry (i64 x) {
if (x == 0) return 0;
if (x <= sqr) return g[id0[x]];
else return g[id1[n / x]];
}
void main(i64 _n) {
n = _n;
sqr = sqrt(n) + 1;
init(sqr);
for(LL l = 1, r = 1; l <= n; l = r = r + 1) {
LL tmp = n / l;
r = n / tmp;
val[++ num] = tmp;
if(tmp <= sqr) id0[tmp] = num;
else id1[n / tmp] = num;
}
for(int i = 1; i <= num; i ++) g[i] = val[i] - 1;
for(int j = 1; j <= tot; j ++) {
int pj = p[j];
for(int i = 1; i <= num; i ++) {
if(val[i] / pj < pj) break;
g[i] = g[i] - g[pos(val[i] / pj)] + j - 1;
}
}
//cout << g[1] << endl;
//return 0;
}
}
i64 n;
inline int f(i64 m) {
if (m <= 2) return 1;
if (m == 3) return 3;
// calc [m / 2 + 1, m]
i64 cnt = Min25 :: qry(m) - Min25 :: qry(m / 2);
return (m - cnt - 1) % P * power (m, cnt % (P - 1)) % P;
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
Min25 :: main(n);
i64 ans = 1;
for (i64 l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
ans = 1ll * ans * power (f(n / l), r - l + 1) % P;
}
cout << ans << '\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 9812kb
input:
4
output:
8
result:
ok answer is '8'
Test #2:
score: 0
Accepted
time: 1ms
memory: 7728kb
input:
2
output:
1
result:
ok answer is '1'
Test #3:
score: 0
Accepted
time: 1ms
memory: 9800kb
input:
123
output:
671840470
result:
ok answer is '671840470'
Test #4:
score: 0
Accepted
time: 1ms
memory: 9804kb
input:
233
output:
353738465
result:
ok answer is '353738465'
Test #5:
score: 0
Accepted
time: 1ms
memory: 9804kb
input:
5981
output:
970246821
result:
ok answer is '970246821'
Test #6:
score: 0
Accepted
time: 1ms
memory: 9812kb
input:
86422
output:
897815688
result:
ok answer is '897815688'
Test #7:
score: 0
Accepted
time: 1ms
memory: 9948kb
input:
145444
output:
189843901
result:
ok answer is '189843901'
Test #8:
score: 0
Accepted
time: 0ms
memory: 9768kb
input:
901000
output:
819449452
result:
ok answer is '819449452'
Test #9:
score: 0
Accepted
time: 0ms
memory: 9776kb
input:
1000000
output:
113573943
result:
ok answer is '113573943'
Test #10:
score: 0
Accepted
time: 3ms
memory: 11908kb
input:
23333333
output:
949849384
result:
ok answer is '949849384'
Test #11:
score: 0
Accepted
time: 4ms
memory: 10020kb
input:
102850434
output:
604886751
result:
ok answer is '604886751'
Test #12:
score: 0
Accepted
time: 15ms
memory: 10468kb
input:
998244353
output:
0
result:
ok answer is '0'
Test #13:
score: 0
Accepted
time: 16ms
memory: 12544kb
input:
1000000007
output:
318420284
result:
ok answer is '318420284'
Test #14:
score: 0
Accepted
time: 20ms
memory: 12604kb
input:
2147483547
output:
688759898
result:
ok answer is '688759898'
Test #15:
score: -100
Wrong Answer
time: 40ms
memory: 16748kb
input:
5120103302
output:
384994873
result:
wrong answer expected '116870489', found '384994873'