QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#97521	#5817. 小学生数学题	sichengzhou	100 ✓	616ms	241568kb	C++14	794b	2023-04-17 04:53:57	2023-04-17 04:53:58

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-04-17 04:53:58]
评测

测评结果：100
用时：616ms
内存：241568kb

查看

[2023-04-17 04:53:57]
提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e7+7,mod=998244353;
int n,m;
int p[N],tp;
int pd[N];
LL val[N];
LL ksm(LL x,int y)
{
	LL ret=1;
	while(y)
	{
		if(y&1)
		{
			ret=ret*x%mod;
		}
		x=x*x%mod;
		y>>=1;
	}
	return ret;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=2;i<=n;i++)
	{
		if(pd[i]==0)
		{
			p[++tp]=i;
		}
		for(int j=1;j<=tp&&(LL)p[j]*i<=n;j++)
		{
			pd[p[j]*i]=p[j];
			if(i%p[j]==0)
			{
				break;
			}
		}
	}
	LL cur=1,ans=0;
	for(int i=1;i<=n;i++)
	{
		cur*=i;cur%=mod;
		if(pd[i]==0)
		{
			val[i]=ksm(i,mod-1-m);
		}else{
			val[i]=val[i/pd[i]]*val[pd[i]]%mod;
		}
	//	cout<<cur<<' '<<val[i]<<endl;
		ans+=cur*val[i]%mod;
		ans%=mod;
	}
	printf("%lld\n",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: 281ms

memory: 117640kb

input:

9450395 1

output:

688545438

result:

ok single line: '688545438'

Test #2:

score: 10

Accepted

time: 265ms

memory: 113488kb

input:

8978812 1

output:

334565356

result:

ok single line: '334565356'

Test #3:

score: 10

Accepted

time: 254ms

memory: 112612kb

input:

8944235 1

output:

982802915

result:

ok single line: '982802915'

Test #4:

score: 10

Accepted

time: 197ms

memory: 91516kb

input:

7081118 3

output:

599009773

result:

ok single line: '599009773'

Test #5:

score: 10

Accepted

time: 231ms

memory: 101056kb

input:

7904241 3

output:

871243720

result:

ok single line: '871243720'

Test #6:

score: 10

Accepted

time: 298ms

memory: 125164kb

input:

9921275 3

output:

549818101

result:

ok single line: '549818101'

Test #7:

score: 10

Accepted

time: 533ms

memory: 216724kb

input:

17575748 14135489

output:

69236780

result:

ok single line: '69236780'

Test #8:

score: 10

Accepted

time: 616ms

memory: 241568kb

input:

19858362 14822524

output:

239890381

result:

ok single line: '239890381'

Test #9:

score: 10

Accepted

time: 591ms

memory: 230288kb

input:

18848696 15530895

output:

88125041

result:

ok single line: '88125041'

Test #10:

score: 10

Accepted

time: 525ms

memory: 219256kb

input:

17787945 13890407

output:

989967864

result:

ok single line: '989967864'

Extra Test:

score: 0

Extra Test Passed