QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#574845 | #9309. Graph | gxy001 | WA | 48ms | 8012kb | C++23 | 1.2kb | 2024-09-19 01:37:48 | 2024-09-19 01:37:48 |
Judging History
answer
#include<iostream>
#include<cmath>
using std::cin,std::cout;
int const mod=998244353;
int pow(int x,int y){
int res=1;
while(y){
if(y&1) res=1ll*res*x%mod;
x=1ll*x*x%mod,y>>=1;
}
return res;
}
int f0[400010],t,m;
long long n,f1[400010];
auto divide=[](long long N,long long d)->int{return double(N)/d;};
inline long long get(long long x){
return x<=m?f0[x]:f1[divide(n,x)];
}
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n;
m=std::sqrt(n);
for(int i=1;i<=m;i++){
f0[i]=i;
f1[i]=(n/i);
}
for(int i=2;i<=m;i++)if(f0[i]!=f0[i-1]){
int x=f0[i-1];
long long r=1ll*i*i;
int u=std::min(1ll*m,n/r),uu=std::min(u,divide(m,i));
for(int j=1;j<=uu;j++) f1[j]=f1[j]-f1[i*j]+x;
long long t=n/i;
for(int j=uu+1;j<=u;j++) f1[j]=f1[j]-f0[divide(t,j)]+x;
for(int j=m;j>=r;j--) f0[j]=f0[j]-f0[divide(j,i)]+x;
}
int ans=1;
for(long long l=1,r;l<=n;l=r+1){
r=n/(n/l);
long long u=n/l;
if(u==1) break;
long long k=get(u)-get(u/2);
int f=1ll*pow(int(u%mod),int(k%(mod-2)))*((u-k-1)%mod)%mod;
if(u==2) f=1;
if(u==3) f=3;
ans=1ll*ans*pow(f,int((r-l+1)%(mod-2)))%mod;
}
cout<<ans<<'\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5684kb
input:
4
output:
8
result:
ok answer is '8'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5648kb
input:
2
output:
1
result:
ok answer is '1'
Test #3:
score: 0
Accepted
time: 1ms
memory: 5652kb
input:
123
output:
671840470
result:
ok answer is '671840470'
Test #4:
score: 0
Accepted
time: 1ms
memory: 5676kb
input:
233
output:
353738465
result:
ok answer is '353738465'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
5981
output:
970246821
result:
ok answer is '970246821'
Test #6:
score: 0
Accepted
time: 1ms
memory: 5676kb
input:
86422
output:
897815688
result:
ok answer is '897815688'
Test #7:
score: 0
Accepted
time: 1ms
memory: 5708kb
input:
145444
output:
189843901
result:
ok answer is '189843901'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3676kb
input:
901000
output:
819449452
result:
ok answer is '819449452'
Test #9:
score: 0
Accepted
time: 1ms
memory: 5656kb
input:
1000000
output:
113573943
result:
ok answer is '113573943'
Test #10:
score: 0
Accepted
time: 1ms
memory: 5712kb
input:
23333333
output:
949849384
result:
ok answer is '949849384'
Test #11:
score: 0
Accepted
time: 3ms
memory: 5800kb
input:
102850434
output:
604886751
result:
ok answer is '604886751'
Test #12:
score: 0
Accepted
time: 9ms
memory: 7804kb
input:
998244353
output:
0
result:
ok answer is '0'
Test #13:
score: 0
Accepted
time: 8ms
memory: 4100kb
input:
1000000007
output:
318420284
result:
ok answer is '318420284'
Test #14:
score: 0
Accepted
time: 14ms
memory: 8012kb
input:
2147483547
output:
688759898
result:
ok answer is '688759898'
Test #15:
score: 0
Accepted
time: 23ms
memory: 7872kb
input:
5120103302
output:
116870489
result:
ok answer is '116870489'
Test #16:
score: -100
Wrong Answer
time: 48ms
memory: 7184kb
input:
19834593299
output:
572746876
result:
wrong answer expected '523663743', found '572746876'