QOJ.ac

QOJ

The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#287989	#5817. 小学生数学题	Haoyue_06432	100 ✓	478ms	192008kb	C++14	738b	2023-12-21 14:13:00	2023-12-21 14:13:01

Judging History

This is the latest submission verdict.

[2023-12-21 14:13:01]
Judged

Verdict: 100
Time: 478ms
Memory: 192008kb

Show

[2023-12-21 14:13:00]
Submitted

answer

#include<bits/stdc++.h>
#define ll long long
#define maxn 20000005
#define inf 1e18
#define mod 998244353
using namespace std;
ll n,m,ans1=1,inv[maxn],zs[maxn],cnt,ans;
bool bj[maxn];
ll ksm(ll x,ll y)
{
	ll ans=1;
	while(y)
	{
		if(y%2==1)ans=(ans*x)%mod;
		x=(x*x)%mod;
		y/=2;
	}
	return ans;
}
int main()
{
	cin>>n>>m;
	inv[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(!bj[i])
		{
			bj[i]=true;
			inv[i]=ksm(ksm(i,m),mod-2);
			zs[++cnt]=i;
		}
		for(int j=1;j<=cnt&&zs[j]*i<=n;j++)
		{
			bj[zs[j]*i]=true;
			inv[zs[j]*i]=(inv[zs[j]]*inv[i])%mod;
			if(i%zs[j]==0)break;
		}
	}
	for(int i=1;i<=n;i++)
	{
		ans1=(ans1*i)%mod;
		ans=(ans+ans1*inv[i]%mod)%mod;
	}
	cout<<ans;
	return 0;
}
/*
*/

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10

Accepted

time: 172ms

memory: 95684kb

input:

9450395 1

output:

688545438

result:

ok single line: '688545438'

Test #2:

score: 10

Accepted

time: 156ms

memory: 91436kb

input:

8978812 1

output:

334565356

result:

ok single line: '334565356'

Test #3:

score: 10

Accepted

time: 159ms

memory: 90624kb

input:

8944235 1

output:

982802915

result:

ok single line: '982802915'

Test #4:

score: 10

Accepted

time: 129ms

memory: 75068kb

input:

7081118 3

output:

599009773

result:

ok single line: '599009773'

Test #5:

score: 10

Accepted

time: 142ms

memory: 81628kb

input:

7904241 3

output:

871243720

result:

ok single line: '871243720'

Test #6:

score: 10

Accepted

time: 175ms

memory: 100336kb

input:

9921275 3

output:

549818101

result:

ok single line: '549818101'

Test #7:

score: 10

Accepted

time: 411ms

memory: 171936kb

input:

17575748 14135489

output:

69236780

result:

ok single line: '69236780'

Test #8:

score: 10

Accepted

time: 478ms

memory: 192008kb

input:

19858362 14822524

output:

239890381

result:

ok single line: '239890381'

Test #9:

score: 10

Accepted

time: 454ms

memory: 182720kb

input:

18848696 15530895

output:

88125041

result:

ok single line: '88125041'

Test #10:

score: 10

Accepted

time: 431ms

memory: 173116kb

input:

17787945 13890407

output:

989967864

result:

ok single line: '989967864'

Extra Test:

score: 0

Extra Test Passed