QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#567501 | #9309. Graph | chsuhan | AC ✓ | 1212ms | 91476kb | C++14 | 925b | 2024-09-16 12:20:59 | 2024-09-16 12:21:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=10000007,P=998244353;
unordered_map<int,int>mp;
int n,sp[N];
vector<int>p;
int pw(int x,int y){
int z=1;
x%=P;
for(;y>0;y>>=1){
if(y&1)z=z*x%P;
x=x*x%P;
}
return z;
}
int sp_(int x){
if(x<N)return sp[x];
return mp[x];
}
void getsp(){
for(int i=1;p[i]*p[i]<=n;i++)
for(int j=n;j>=p[i]*p[i];j=n/(n/j+1))
(j<N?sp[j]:mp[j])-=sp_(j/p[i])-sp[p[i-1]];
}
int f(int x){
if(x<=3)return pw(x,x-2);
int m=sp_(x)-sp_(x/2)+2;
return (x-m+1)%P*pw(x,m-2)%P;
}
signed main(){
cin>>n;
p.push_back(1);
for(int i=2;i<N;i++){
if(sp[i])continue;
p.push_back(i);
for(int j=i*i;j<N;j+=i)sp[j]=1;
}
for(int i=n;i>1;i=n/(n/i+1)){
if(i<N)sp[i]=i-1;
else mp[i]=i-1;
}
getsp();
int ans=1;
for(int l=1,r;l<=n;l=r+1){
r=n/(n/l);
ans=ans*pw(f(n/l),r-l+1)%P;
}
cout<<ans;
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 150ms
memory: 90152kb
input:
4
output:
8
result:
ok answer is '8'
Test #2:
score: 0
Accepted
time: 151ms
memory: 90220kb
input:
2
output:
1
result:
ok answer is '1'
Test #3:
score: 0
Accepted
time: 156ms
memory: 90200kb
input:
123
output:
671840470
result:
ok answer is '671840470'
Test #4:
score: 0
Accepted
time: 157ms
memory: 90208kb
input:
233
output:
353738465
result:
ok answer is '353738465'
Test #5:
score: 0
Accepted
time: 151ms
memory: 89864kb
input:
5981
output:
970246821
result:
ok answer is '970246821'
Test #6:
score: 0
Accepted
time: 154ms
memory: 91476kb
input:
86422
output:
897815688
result:
ok answer is '897815688'
Test #7:
score: 0
Accepted
time: 139ms
memory: 91264kb
input:
145444
output:
189843901
result:
ok answer is '189843901'
Test #8:
score: 0
Accepted
time: 148ms
memory: 90736kb
input:
901000
output:
819449452
result:
ok answer is '819449452'
Test #9:
score: 0
Accepted
time: 157ms
memory: 90388kb
input:
1000000
output:
113573943
result:
ok answer is '113573943'
Test #10:
score: 0
Accepted
time: 153ms
memory: 90044kb
input:
23333333
output:
949849384
result:
ok answer is '949849384'
Test #11:
score: 0
Accepted
time: 154ms
memory: 90924kb
input:
102850434
output:
604886751
result:
ok answer is '604886751'
Test #12:
score: 0
Accepted
time: 185ms
memory: 90620kb
input:
998244353
output:
0
result:
ok answer is '0'
Test #13:
score: 0
Accepted
time: 202ms
memory: 90364kb
input:
1000000007
output:
318420284
result:
ok answer is '318420284'
Test #14:
score: 0
Accepted
time: 213ms
memory: 90888kb
input:
2147483547
output:
688759898
result:
ok answer is '688759898'
Test #15:
score: 0
Accepted
time: 278ms
memory: 90568kb
input:
5120103302
output:
116870489
result:
ok answer is '116870489'
Test #16:
score: 0
Accepted
time: 473ms
memory: 90164kb
input:
19834593299
output:
523663743
result:
ok answer is '523663743'
Test #17:
score: 0
Accepted
time: 794ms
memory: 90720kb
input:
52500109238
output:
195086665
result:
ok answer is '195086665'
Test #18:
score: 0
Accepted
time: 1069ms
memory: 89804kb
input:
84848352911
output:
107959260
result:
ok answer is '107959260'
Test #19:
score: 0
Accepted
time: 1205ms
memory: 89784kb
input:
99824435322
output:
0
result:
ok answer is '0'
Test #20:
score: 0
Accepted
time: 1212ms
memory: 91328kb
input:
99999999354
output:
316301711
result:
ok answer is '316301711'
Test #21:
score: 0
Accepted
time: 1204ms
memory: 89660kb
input:
100000000000
output:
396843576
result:
ok answer is '396843576'
Extra Test:
score: 0
Extra Test Passed