QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#601393 | #9309. Graph | Ashbourne | WA | 11ms | 21020kb | C++14 | 1.7kb | 2024-09-29 22:53:49 | 2024-09-29 22:53:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, j, k) for(int i = j; i <= k; ++ i)
#define drp(i, j, k) for(int i = j; i >= k; -- i)
const int N = 8e5 + 10, Mod = 998244353;
int fpow(int a, int b){
int x = 1;
while(b){
if(b & 1) x = x * a % Mod;
a = a * a % Mod;
b >>= 1;
}
return x;
}
int inv2;
int pri[N], ispri[N], b[N][2], c[N], g[N], w[N], P, E;
void prpr(int n){
inv2 = fpow(2, Mod - 2);
rep(i, 1, n) ispri[i] = 1;
rep(i, 2, n){
if(ispri[i]){
pri[++P] = i;
// c[P] = (c[P - 1] + 1);
}
rep(j, 1, P){
if(i * pri[j] > n) break;
ispri[i * pri[j]] = 0;
if(i % pri[j] == 0) break;
}
}
}
int ans = 1, z[N];
#define id(x) (x <= E ? b[x][0]: b[n / (x)][1])
void calc(int n){
E = sqrt(n);
int t = 0, l = 1, r, q;
for(; l <= n; l = r + 1){
q = w[id(n / l) = ++ t] = n / l; r = (n / q);
z[t] = (r - l + 1);
int num = w[t] % Mod;
g[t] = num + Mod - 1;
g[t] %= Mod;
// g[t] = (g[t] + Mod - 1) % Mod;
}
// cout << t << endl;
// rep(i, 1, t) cout << g[i] << endl;
// t--;
rep(i, 1, P) rep(j, 1, t){
if(pri[i] * pri[i] > w[j]) break;
q = id(w[j] / pri[i]);
g[j] = (g[j] - g[q] + i - 1 + Mod) % Mod;
}
rep(i, 1, t){
q = id(w[i] / 2);
g[i] = (g[i] - g[q] + Mod) % Mod;
}
// rep(i, 1, t) cout << g[i] << endl;
rep(i, 1, t - 1){
int m = w[i] % Mod;
int f_tt = (m - g[i] - 1) % Mod * fpow(m, g[i]) % Mod;
if(m - g[i] - 1 == 0) f_tt = fpow(m, g[i] - 1);
// cout << f_tt << endl;
ans = ans * fpow(f_tt, z[i]) % Mod;
}
// ans = ans * fpow(fpow(w[t - 1], g[t - 1] - 1), z[t - 1]) % Mod;
cout << ans << endl;
}
signed main(){
ios::sync_with_stdio(0);
prpr(4e5);
int n; cin >> n;
calc(n);
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 15968kb
input:
4
output:
8
result:
ok answer is '8'
Test #2:
score: 0
Accepted
time: 5ms
memory: 17976kb
input:
2
output:
1
result:
ok answer is '1'
Test #3:
score: 0
Accepted
time: 4ms
memory: 13892kb
input:
123
output:
671840470
result:
ok answer is '671840470'
Test #4:
score: 0
Accepted
time: 4ms
memory: 15968kb
input:
233
output:
353738465
result:
ok answer is '353738465'
Test #5:
score: 0
Accepted
time: 4ms
memory: 13856kb
input:
5981
output:
970246821
result:
ok answer is '970246821'
Test #6:
score: 0
Accepted
time: 4ms
memory: 13876kb
input:
86422
output:
897815688
result:
ok answer is '897815688'
Test #7:
score: 0
Accepted
time: 4ms
memory: 15952kb
input:
145444
output:
189843901
result:
ok answer is '189843901'
Test #8:
score: 0
Accepted
time: 5ms
memory: 15976kb
input:
901000
output:
819449452
result:
ok answer is '819449452'
Test #9:
score: 0
Accepted
time: 4ms
memory: 13920kb
input:
1000000
output:
113573943
result:
ok answer is '113573943'
Test #10:
score: 0
Accepted
time: 6ms
memory: 16120kb
input:
23333333
output:
949849384
result:
ok answer is '949849384'
Test #11:
score: 0
Accepted
time: 0ms
memory: 18280kb
input:
102850434
output:
604886751
result:
ok answer is '604886751'
Test #12:
score: 0
Accepted
time: 11ms
memory: 21020kb
input:
998244353
output:
0
result:
ok answer is '0'
Test #13:
score: -100
Wrong Answer
time: 11ms
memory: 18804kb
input:
1000000007
output:
-679824069
result:
wrong answer expected '318420284', found '-679824069'