QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#300799	#5817. 小学生数学题	ebofan^#	100 ✓	485ms	184616kb	C++14	706b	2024-01-08 20:11:36	2024-07-04 03:17:03

Judging History

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

[2024-07-04 03:17:03]
评测

测评结果：100
用时：485ms
内存：184616kb

查看

[2024-01-08 20:11:36]
提交

answer

#include<iostream>
#define ll long long
using namespace std;
constexpr ll p = 998244353;
int k;
ll n,ans;
ll jc = 1,fm;
ll inv[20000010];
bool vis[20000010];
int pr[20000010],cnt;
ll mypow(ll x,int tms){
	ll ans = 1;
	while(tms){
		if(tms&1) ans = ans*x%p;
		x=x*x%p;
		tms>>=1;
	}
	return ans;
}
int main(){
	cin>>n>>k;
	inv[1]=1;
	for(int i=2;i<=n;i++){
		if(!vis[i]){
			inv[i]=mypow(mypow(i,k),p-2);
			pr[++cnt]=i;
		}
		for(int j=1;1ll*i*pr[j]<=n;j++){
			vis[i*pr[j]]=1;
			inv[i*pr[j]]=inv[i]*inv[pr[j]]%p;
			if(i%pr[j]==0) break;
		}
	}
	for(int i=1;i<=n;i++){
		jc = jc*i%p;
		ans += jc * inv[i] % p;
		if(ans>=p) ans-=p;
	}
	cout<<ans<<endl;
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10

Accepted

time: 176ms

memory: 93296kb

input:

9450395 1

output:

688545438

result:

ok single line: '688545438'

Test #2:

score: 10

Accepted

time: 176ms

memory: 89608kb

input:

8978812 1

output:

334565356

result:

ok single line: '334565356'

Test #3:

score: 10

Accepted

time: 170ms

memory: 89364kb

input:

8944235 1

output:

982802915

result:

ok single line: '982802915'

Test #4:

score: 10

Accepted

time: 132ms

memory: 72244kb

input:

7081118 3

output:

599009773

result:

ok single line: '599009773'

Test #5:

score: 10

Accepted

time: 153ms

memory: 77796kb

input:

7904241 3

output:

871243720

result:

ok single line: '871243720'

Test #6:

score: 10

Accepted

time: 194ms

memory: 96156kb

input:

9921275 3

output:

549818101

result:

ok single line: '549818101'

Test #7:

score: 10

Accepted

time: 425ms

memory: 166608kb

input:

17575748 14135489

output:

69236780

result:

ok single line: '69236780'

Test #8:

score: 10

Accepted

time: 485ms

memory: 184616kb

input:

19858362 14822524

output:

239890381

result:

ok single line: '239890381'

Test #9:

score: 10

Accepted

time: 458ms

memory: 177652kb

input:

18848696 15530895

output:

88125041

result:

ok single line: '88125041'

Test #10:

score: 10

Accepted

time: 441ms

memory: 169384kb

input:

17787945 13890407

output:

989967864

result:

ok single line: '989967864'

Extra Test:

score: 0

Extra Test Passed