QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#289305	#5817. 小学生数学题	Michstabe	100 ✓	482ms	327888kb	C++14	802b	2023-12-23 16:48:30	2023-12-23 16:48:31

Judging History

你现在查看的是最新测评结果

[2023-12-23 16:48:31]
评测

测评结果：100
用时：482ms
内存：327888kb

查看

[2023-12-23 16:48:30]
提交

answer

#include<iostream>
using namespace std;
const long long mod=998244353,N=2*1e7+20;
long long n,k,cnt,ans,jc,inv[N],pr[N],pri[N];
long long ksm(long long x,long long y){
    long long z=1;
    while(y){
        if(y&1) z=z*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return z;
}
int main(){
    int i,j;
    cin>>n>>k;
    inv[1]=1;
    for(i=2;i<=n;i++){
        if(!pri[i]){
            pri[i]=i; 
            pr[++cnt]=i; 
            inv[i]=ksm(ksm(i,mod-2),k); 
        }
        for(j=1;pr[j]*i<=n&&j<=cnt&&pr[j]<=pri[i];j++){
            pri[pr[j]*i]=pr[j]; 
            inv[pr[j]*i]=inv[pr[j]]*inv[i]%mod;
        }
    }
    jc=1; 
    for(i=1;i<=n;i++){
        ans=(ans+jc*inv[i]%mod)%mod;
        jc=jc*(i+1)%mod;
    }
    cout<<ans;
    return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 10

Accepted

time: 175ms

memory: 164648kb

input:

9450395 1

output:

688545438

result:

ok single line: '688545438'

Test #2:

score: 10

Accepted

time: 171ms

memory: 151612kb

input:

8978812 1

output:

334565356

result:

ok single line: '334565356'

Test #3:

score: 10

Accepted

time: 172ms

memory: 153668kb

input:

8944235 1

output:

982802915

result:

ok single line: '982802915'

Test #4:

score: 10

Accepted

time: 135ms

memory: 120528kb

input:

7081118 3

output:

599009773

result:

ok single line: '599009773'

Test #5:

score: 10

Accepted

time: 153ms

memory: 136804kb

input:

7904241 3

output:

871243720

result:

ok single line: '871243720'

Test #6:

score: 10

Accepted

time: 198ms

memory: 170816kb

input:

9921275 3

output:

549818101

result:

ok single line: '549818101'

Test #7:

score: 10

Accepted

time: 439ms

memory: 292084kb

input:

17575748 14135489

output:

69236780

result:

ok single line: '69236780'

Test #8:

score: 10

Accepted

time: 482ms

memory: 327888kb

input:

19858362 14822524

output:

239890381

result:

ok single line: '239890381'

Test #9:

score: 10

Accepted

time: 455ms

memory: 314288kb

input:

18848696 15530895

output:

88125041

result:

ok single line: '88125041'

Test #10:

score: 10

Accepted

time: 431ms

memory: 294056kb

input:

17787945 13890407

output:

989967864

result:

ok single line: '989967864'

Extra Test:

score: 0

Extra Test Passed