QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#503679	#5817. 小学生数学题	badn	100 ✓	453ms	488044kb	C++14	672b	2024-08-03 23:00:29	2024-08-03 23:00:30

Judging History

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

[2024-08-03 23:00:30]
评测

测评结果：100
用时：453ms
内存：488044kb

查看

[2024-08-03 23:00:29]
提交

answer

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=998244353;
ll power(ll a,ll b){
	ll ans=1;
	while(b){
		if(b&1) ans=ans*a%mod;	
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
ll n,k,fac[20000010],ans=1,vis[20000010],f[20000010],c;
vector<ll>pr;
int main(){
	scanf("%lld%lld",&n,&k);
	fac[1]=1;
	for(ll i=2;i<=n;i++) fac[i]=fac[i-1]*i%mod;
	c=k*(mod-2)%(mod-1);
	for(ll i=2;i<=n;i++){
		if(!vis[i]) pr.push_back(i),f[i]=power(i,c);
		for(ll v:pr){
			if(v*i>n) break;
			vis[i*v]=1;
			f[i*v]=f[i]*f[v]%mod;
			if(i%v==0) break;
		}
	}
	for(ll i=2;i<=n;i++)
		ans=(ans+fac[i]*f[i]%mod)%mod;
	cout<<ans;
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Pretests

Final Tests

Test #1:

score: 10

Accepted

time: 215ms

memory: 237948kb

input:

9450395 1

output:

688545438

result:

ok single line: '688545438'

Test #2:

score: 10

Accepted

time: 206ms

memory: 227292kb

input:

8978812 1

output:

334565356

result:

ok single line: '334565356'

Test #3:

score: 10

Accepted

time: 213ms

memory: 226016kb

input:

8944235 1

output:

982802915

result:

ok single line: '982802915'

Test #4:

score: 10

Accepted

time: 168ms

memory: 179532kb

input:

7081118 3

output:

599009773

result:

ok single line: '599009773'

Test #5:

score: 10

Accepted

time: 189ms

memory: 199544kb

input:

7904241 3

output:

871243720

result:

ok single line: '871243720'

Test #6:

score: 10

Accepted

time: 210ms

memory: 246248kb

input:

9921275 3

output:

549818101

result:

ok single line: '549818101'

Test #7:

score: 10

Accepted

time: 396ms

memory: 436656kb

input:

17575748 14135489

output:

69236780

result:

ok single line: '69236780'

Test #8:

score: 10

Accepted

time: 453ms

memory: 488044kb

input:

19858362 14822524

output:

239890381

result:

ok single line: '239890381'

Test #9:

score: 10

Accepted

time: 436ms

memory: 465656kb

input:

18848696 15530895

output:

88125041

result:

ok single line: '88125041'

Test #10:

score: 10

Accepted

time: 405ms

memory: 440160kb

input:

17787945 13890407

output:

989967864

result:

ok single line: '989967864'

Extra Test:

score: 0

Extra Test Passed