QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#89290#5817. 小学生数学题cyl001100 ✓411ms107156kbC++14720b2023-03-19 15:54:062023-03-19 15:54:09

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-19 15:54:09]
  • 评测
  • 测评结果:100
  • 用时:411ms
  • 内存:107156kb
  • [2023-03-19 15:54:06]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 2e7 + 5,p = 998244353;
int n,k,tot,sum,fac,mi[N],pr[N];
bool f[N];
int ksm(int x,int y)
{
	int ret = 1;
	while(y)
	{
		if(y & 1) ret = 1LL * ret * x % p;
		x = 1LL * x * x % p;
		y >>= 1;
	}
	return ret;
}
int main()
{
	scanf("%d%d",&n,&k);
	fac = mi[1] = sum = 1;
	for(int i = 2;i <= n;i++)
	{
		fac = 1LL * fac * i % p;
		if(!f[i])
		{
			mi[i] = ksm(i,p - 1 - k);
			pr[++tot] = i;
		}
		sum = (sum + 1LL * fac * mi[i] % p) % p;
		for(int j = 1;j <= tot && pr[j] * i <= n;j++)
		{
			mi[i * pr[j]] = 1LL * mi[i] * mi[pr[j]] % p;
			f[i * pr[j]] = 1;
			if(i % pr[j] == 0) break;
		}
	}
	printf("%d\n",sum);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 192ms
memory: 56336kb

input:

9450395 1

output:

688545438

result:

ok single line: '688545438'

Test #2:

score: 10
Accepted
time: 187ms
memory: 55396kb

input:

8978812 1

output:

334565356

result:

ok single line: '334565356'

Test #3:

score: 10
Accepted
time: 186ms
memory: 56112kb

input:

8944235 1

output:

982802915

result:

ok single line: '982802915'

Test #4:

score: 10
Accepted
time: 140ms
memory: 46868kb

input:

7081118 3

output:

599009773

result:

ok single line: '599009773'

Test #5:

score: 10
Accepted
time: 162ms
memory: 48344kb

input:

7904241 3

output:

871243720

result:

ok single line: '871243720'

Test #6:

score: 10
Accepted
time: 198ms
memory: 55264kb

input:

9921275 3

output:

549818101

result:

ok single line: '549818101'

Test #7:

score: 10
Accepted
time: 374ms
memory: 96160kb

input:

17575748 14135489

output:

69236780

result:

ok single line: '69236780'

Test #8:

score: 10
Accepted
time: 411ms
memory: 107156kb

input:

19858362 14822524

output:

239890381

result:

ok single line: '239890381'

Test #9:

score: 10
Accepted
time: 398ms
memory: 101676kb

input:

18848696 15530895

output:

88125041

result:

ok single line: '88125041'

Test #10:

score: 10
Accepted
time: 395ms
memory: 96544kb

input:

17787945 13890407

output:

989967864

result:

ok single line: '989967864'

Extra Test:

score: 0
Extra Test Passed