QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#719663	#5817. 小学生数学题	Leonador	100 ✓	328ms	195164kb	C++14	661b	2024-11-07 07:16:24	2024-11-07 07:16:24

Judging History

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

[2024-11-07 07:16:24]
评测

测评结果：100
用时：328ms
内存：195164kb

查看

[2024-11-07 07:16:24]
提交

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define N (int)(2e7+10)
#define mod 998244353

int n,k,ans=1;
int pk[N];
bool vis[N];

vector<int>p;

inline int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=res*a%mod;
		b>>=1;a=a*a%mod;
	}
	return res;
}

signed main(){
	scanf("%lld %lld",&n,&k);
	int fac=1,c=k*(mod-2)%(mod-1);
	for(int i=2;i<=n;++i){
		if(!vis[i]) p.push_back(i),pk[i]=qpow(i,c);
		for(int v:p){
			if(v*i>n) break;
			vis[v*i]=1;
			pk[v*i]=pk[v]*pk[i]%mod;
			if(i%v==0) break;
		}
		fac=fac*i%mod;
		ans=(ans+fac*pk[i]%mod)%mod;
	}
	printf("%lld\n",ans);
	return 0;
}

源文件, 语言: C++14

詳細信息

Pretests

Final Tests

Test #1:

score: 10

Accepted

time: 168ms

memory: 97740kb

input:

9450395 1

output:

688545438

result:

ok single line: '688545438'

Test #2:

score: 10

Accepted

time: 149ms

memory: 92952kb

input:

8978812 1

output:

334565356

result:

ok single line: '334565356'

Test #3:

score: 10

Accepted

time: 155ms

memory: 95568kb

input:

8944235 1

output:

982802915

result:

ok single line: '982802915'

Test #4:

score: 10

Accepted

time: 115ms

memory: 72164kb

input:

7081118 3

output:

599009773

result:

ok single line: '599009773'

Test #5:

score: 10

Accepted

time: 132ms

memory: 85072kb

input:

7904241 3

output:

871243720

result:

ok single line: '871243720'

Test #6:

score: 10

Accepted

time: 165ms

memory: 102108kb

input:

9921275 3

output:

549818101

result:

ok single line: '549818101'

Test #7:

score: 10

Accepted

time: 294ms

memory: 179396kb

input:

17575748 14135489

output:

69236780

result:

ok single line: '69236780'

Test #8:

score: 10

Accepted

time: 326ms

memory: 195164kb

input:

19858362 14822524

output:

239890381

result:

ok single line: '239890381'

Test #9:

score: 10

Accepted

time: 328ms

memory: 187688kb

input:

18848696 15530895

output:

88125041

result:

ok single line: '88125041'

Test #10:

score: 10

Accepted

time: 309ms

memory: 179952kb

input:

17787945 13890407

output:

989967864

result:

ok single line: '989967864'

Extra Test:

score: 0

Extra Test Passed