QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #574834 | #9309. Graph | NTT | TL | 587ms | 807076kb | C++23 | 818b | 2024-09-19 01:16:04 | 2024-09-19 01:16:05 |
Judging History
answer
#pragma GCC optimize("Ofast,inline,unroll-loops")
#include<bits/stdc++.h>
using ll=long long;
constexpr int N=100005000,M=998244353;
auto qpow(ll a,auto b){int res=1;for(;b;a=a*a%M,b>>=1)if(b&1)res=res*a%M;return res;}
int v[N],pi[N];
std::vector<int>prime;
signed main(){
v[1]=1;
for(int i=2;i<N;++i){
pi[i]=pi[i-1];
if(!v[i]){
v[i]=i;
++pi[i];
prime.emplace_back(i);
}
for(auto&p:prime){
if(i*p>=N)break;
v[i*p]=p;
if(v[i]==p)break;
}
}
ll n;
std::cin>>n;
ll ans=1;
for(ll l=1,r;l<=n;l=r+1){
ll q=n/l;
r=n/q;
// std::cerr<<l<<' '<<r<<' '<<q<<'\n';
ans=(ans*qpow([&]->ll{
if(q==1)return 1;
if(q==2)return 1;
if(q==3)return 3;
int c=pi[q]-pi[q/2];
return qpow(q,c)*(q-c-1)%M;
}()%M,r-l+1))%M;
}
printf("%lld\n",ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 587ms
memory: 806984kb
input:
4
output:
8
result:
ok answer is '8'
Test #2:
score: 0
Accepted
time: 555ms
memory: 806916kb
input:
2
output:
1
result:
ok answer is '1'
Test #3:
score: 0
Accepted
time: 520ms
memory: 806896kb
input:
123
output:
671840470
result:
ok answer is '671840470'
Test #4:
score: 0
Accepted
time: 519ms
memory: 807016kb
input:
233
output:
353738465
result:
ok answer is '353738465'
Test #5:
score: 0
Accepted
time: 528ms
memory: 807008kb
input:
5981
output:
970246821
result:
ok answer is '970246821'
Test #6:
score: 0
Accepted
time: 547ms
memory: 807076kb
input:
86422
output:
897815688
result:
ok answer is '897815688'
Test #7:
score: 0
Accepted
time: 523ms
memory: 806856kb
input:
145444
output:
189843901
result:
ok answer is '189843901'
Test #8:
score: 0
Accepted
time: 544ms
memory: 807032kb
input:
901000
output:
819449452
result:
ok answer is '819449452'
Test #9:
score: 0
Accepted
time: 515ms
memory: 806976kb
input:
1000000
output:
113573943
result:
ok answer is '113573943'
Test #10:
score: 0
Accepted
time: 507ms
memory: 807032kb
input:
23333333
output:
949849384
result:
ok answer is '949849384'
Test #11:
score: -100
Time Limit Exceeded
input:
102850434