QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#620338 | #9309. Graph | sz051 | WA | 273ms | 10460kb | C++20 | 1.7kb | 2024-10-07 17:35:18 | 2024-10-07 17:35:19 |
Judging History
answer
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#define int long long
using namespace std;
const int md=998244353,B=320000;
void read(int &x){
x=0;
int f=1;
char c=getchar();
while(!('0'<=c && c<='9')){
if(c=='-'){
f=-1;
}
c=getchar();
}
while('0'<=c && c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
x*=f;
}
int powr(int b,int k){
b%=md;
int res=1;
for(;k;k>>=1,b=b*b%md){
if(k&1){
res=res*b%md;
}
}
return res;
}
int ps[100010],cnt=0;
bool isp[1000010];
void sieve(int n){
memset(isp,1,sizeof(isp));
isp[0]=isp[1]=0;
for(int i=2;i<=n;i++){
if(isp[i]){
ps[++cnt]=i;
}
for(int j=1;j<=cnt && ps[j]*i<=n;j++){
isp[ps[j]*i]=0;
if(i%ps[j]==0){
break;
}
}
}
}
int n,sum1[1000010],sum2[1000010];
int getres(int k){
if(n/k<=2){
return 1;
}else if(n/k==3){
return 3;
}else{
int cur=((n/k<=B?sum1[n/k]:sum2[k])-(n/(2*k)<=B?sum1[n/(2*k)]:sum2[2*k]))%md;
return (n/k-cur-1)%md*powr(n/k,cur)%md;
}
}
signed main(){
sieve(B);
read(n);
for(int i=1;i<=min(B,n);i++){
sum1[i]=i-1;
}
for(int i=1;i<=B;i++){
if(n/i<=B){
break;
}
sum2[i]=n/i-1;
}
for(int j=1;j<=cnt;j++){
int p=ps[j];
if(p*p>n){
break;
}
for(int i=1;i<=B;i++){
if(n/i<=B){
break;
}
int v=n/i;
if(p*p>v){
break;
}
sum2[i]-=(v/p<=B?sum1[v/p]:sum2[i*p])-j+1;
}
for(int i=B;i;i--){
if(p*p>i){
break;
}
sum1[i]-=sum1[i/p]-j+1;
}
}
int res=1;
for(int l=1,r;l<=n;l=r+1){
r=n/(n/l);
res=res*powr(getres(l),r-l+1)%md;
}
printf("%lld",res);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 7628kb
input:
4
output:
8
result:
ok answer is '8'
Test #2:
score: 0
Accepted
time: 2ms
memory: 6128kb
input:
2
output:
1
result:
ok answer is '1'
Test #3:
score: 0
Accepted
time: 8ms
memory: 10460kb
input:
123
output:
671840470
result:
ok answer is '671840470'
Test #4:
score: 0
Accepted
time: 4ms
memory: 7200kb
input:
233
output:
353738465
result:
ok answer is '353738465'
Test #5:
score: 0
Accepted
time: 22ms
memory: 6760kb
input:
5981
output:
970246821
result:
ok answer is '970246821'
Test #6:
score: 0
Accepted
time: 51ms
memory: 10072kb
input:
86422
output:
897815688
result:
ok answer is '897815688'
Test #7:
score: 0
Accepted
time: 59ms
memory: 7824kb
input:
145444
output:
189843901
result:
ok answer is '189843901'
Test #8:
score: 0
Accepted
time: 67ms
memory: 10440kb
input:
901000
output:
819449452
result:
ok answer is '819449452'
Test #9:
score: 0
Accepted
time: 71ms
memory: 7664kb
input:
1000000
output:
113573943
result:
ok answer is '113573943'
Test #10:
score: 0
Accepted
time: 71ms
memory: 7952kb
input:
23333333
output:
949849384
result:
ok answer is '949849384'
Test #11:
score: 0
Accepted
time: 72ms
memory: 6820kb
input:
102850434
output:
604886751
result:
ok answer is '604886751'
Test #12:
score: 0
Accepted
time: 78ms
memory: 7648kb
input:
998244353
output:
0
result:
ok answer is '0'
Test #13:
score: 0
Accepted
time: 78ms
memory: 10352kb
input:
1000000007
output:
318420284
result:
ok answer is '318420284'
Test #14:
score: 0
Accepted
time: 84ms
memory: 6836kb
input:
2147483547
output:
688759898
result:
ok answer is '688759898'
Test #15:
score: 0
Accepted
time: 94ms
memory: 10316kb
input:
5120103302
output:
116870489
result:
ok answer is '116870489'
Test #16:
score: 0
Accepted
time: 152ms
memory: 10132kb
input:
19834593299
output:
523663743
result:
ok answer is '523663743'
Test #17:
score: -100
Wrong Answer
time: 273ms
memory: 10020kb
input:
52500109238
output:
78396536
result:
wrong answer expected '195086665', found '78396536'