QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#574095 | #9309. Graph | Andyqian7 | TL | 1604ms | 846760kb | C++14 | 1.9kb | 2024-09-18 20:47:17 | 2024-09-18 20:47:17 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
int len, lim, lenp, a[7000000], g[7000000];
const int MOD = 998244353;
const int N = 1e8 + 3;
bitset<N> v;
int p[N >> 2], sum[N];
map<int, int> mp;
void seive()
{
int cnt = 0;
for (int i = 2; i < N; i++)
{
if (!v[i])
p[cnt++] = i;
for (int j = 0; j < cnt && i * p[j] < N; j++)
{
v[i * p[j]] = 1;
if (i % p[j] == 0)
break;
}
}
}
int fp(int x, int k)
{
if (!k)
return 1;
if (k & 1)
return x * fp(x, k - 1) % MOD;
int tmp = fp(x, k >> 1);
return tmp * tmp % MOD;
}
inline int get_index(int n, int x)
{
if (x <= lim)
return x;
else
return len - n / x + 1;
}
int cnt(int n)
{
if (n < N)
return sum[n];
if (mp.count(n))
return mp[n];
lim = sqrt(n);
len = lenp = 0;
for (int i = 1; i <= n; i = a[len] + 1)
{
a[++len] = n / (n / i);
g[len] = a[len] - 1;
}
for (int i = 2; i <= lim; ++i)
{
if (g[i] != g[i - 1])
{
++lenp;
for (int j = len; a[j] >= 1ll * i * i; --j)
g[j] = g[j] - g[get_index(n, a[j] / i)] + lenp - 1;
}
}
mp[n] = g[len];
return g[len];
}
int f(int n)
{
return cnt(n) - cnt(n / 2);
}
int F(int n)
{
if (n <= 2)
return 1;
if (n == 3)
return 3;
int tmp = f(n);
return fp(n % MOD, tmp) * (n % MOD - tmp % MOD - 1 + MOD) % MOD;
}
signed main()
{
seive();
for (int i = 2; i < N; i++)
sum[i] = sum[i - 1] + !v[i];
int n;
cin >> n;
int ans = 1;
for (int l = 1, r; l <= n; l = r + 1)
{
r = n / (n / l);
ans = ans * fp(F(n / l), r - l + 1) % MOD;
}
cout << ans;
}
詳細信息
Test #1:
score: 100
Accepted
time: 509ms
memory: 844484kb
input:
4
output:
8
result:
ok answer is '8'
Test #2:
score: 0
Accepted
time: 492ms
memory: 843876kb
input:
2
output:
1
result:
ok answer is '1'
Test #3:
score: 0
Accepted
time: 474ms
memory: 843976kb
input:
123
output:
671840470
result:
ok answer is '671840470'
Test #4:
score: 0
Accepted
time: 491ms
memory: 843496kb
input:
233
output:
353738465
result:
ok answer is '353738465'
Test #5:
score: 0
Accepted
time: 459ms
memory: 843148kb
input:
5981
output:
970246821
result:
ok answer is '970246821'
Test #6:
score: 0
Accepted
time: 460ms
memory: 844420kb
input:
86422
output:
897815688
result:
ok answer is '897815688'
Test #7:
score: 0
Accepted
time: 471ms
memory: 843176kb
input:
145444
output:
189843901
result:
ok answer is '189843901'
Test #8:
score: 0
Accepted
time: 464ms
memory: 843800kb
input:
901000
output:
819449452
result:
ok answer is '819449452'
Test #9:
score: 0
Accepted
time: 468ms
memory: 843344kb
input:
1000000
output:
113573943
result:
ok answer is '113573943'
Test #10:
score: 0
Accepted
time: 497ms
memory: 843788kb
input:
23333333
output:
949849384
result:
ok answer is '949849384'
Test #11:
score: 0
Accepted
time: 454ms
memory: 844744kb
input:
102850434
output:
604886751
result:
ok answer is '604886751'
Test #12:
score: 0
Accepted
time: 516ms
memory: 844328kb
input:
998244353
output:
0
result:
ok answer is '0'
Test #13:
score: 0
Accepted
time: 497ms
memory: 844428kb
input:
1000000007
output:
318420284
result:
ok answer is '318420284'
Test #14:
score: 0
Accepted
time: 567ms
memory: 845700kb
input:
2147483547
output:
688759898
result:
ok answer is '688759898'
Test #15:
score: 0
Accepted
time: 709ms
memory: 845712kb
input:
5120103302
output:
116870489
result:
ok answer is '116870489'
Test #16:
score: 0
Accepted
time: 1604ms
memory: 846760kb
input:
19834593299
output:
523663743
result:
ok answer is '523663743'
Test #17:
score: -100
Time Limit Exceeded
input:
52500109238