QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#584411 | #9309. Graph | qianyue | WA | 16ms | 14612kb | C++20 | 2.2kb | 2024-09-23 13:57:26 | 2024-09-23 13:57:26 |
Judging History
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'