QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#74442	#3161. Another Coin Weighing Puzzle	541forever	AC ✓	86ms	12064kb	C++14	866b	2023-02-01 19:37:18	2023-02-01 19:37:19

Judging History

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

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

[2023-02-01 19:37:19]
评测

测评结果：AC
用时：86ms
内存：12064kb

查看

[2023-02-01 19:37:18]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000000,mod=998244353;
int m,k,mu[MAXN+5],pri[MAXN+5],tot,no[MAXN+5];
int MUL(int x,int y){
	return (long long)x*y%mod;
}
int poww(int x,int y){
	int sum=1;
	while(y){
		if(y&1){
			sum=MUL(sum,x);
		}
		x=MUL(x,x);
		y>>=1;
	}
	return sum;
}
void prep(){
	mu[1]=1;
	for(int i=2;i<=k;++i){
		if(!no[i]){
			pri[++tot]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=tot;++j){
			if((long long)pri[j]*i>k){
				break;
			}
			no[pri[j]*i]=1;
			if(i%pri[j]==0){
				mu[i*pri[j]]=0;
				break;
			}
			mu[i*pri[j]]=-mu[i];
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin>>m>>k;
	prep();
	long long ans=1;
	for(int i=1;i<=k;++i){
		ans+=MUL(poww((k/i)*2+1,m),mu[i]);
		ans%=mod;
		ans-=mu[i];
		ans%=mod;
		ans+=mod;
		ans%=mod;
	}
	cout<<ans;
	return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 2ms

memory: 5320kb

input:

2 1

output:

result:

ok single line: '9'

Test #2:

score: 0

Accepted

time: 2ms

memory: 5376kb

input:

2 2

output:

result:

ok single line: '17'

Test #3:

score: 0

Accepted

time: 3ms

memory: 5360kb

input:

10000 10000

output:

689223145

result:

ok single line: '689223145'

Test #4:

score: 0

Accepted

time: 0ms

memory: 5324kb

input:

9999 31

output:

986106162

result:

ok single line: '986106162'

Test #5:

score: 0

Accepted

time: 0ms

memory: 5380kb

input:

57 9817

output:

447253096

result:

ok single line: '447253096'

Test #6:

score: 0

Accepted

time: 2ms

memory: 5348kb

input:

501 499

output:

247755220

result:

ok single line: '247755220'

Test #7:

score: 0

Accepted

time: 13ms

memory: 8284kb

input:

97424 174829

output:

964884269

result:

ok single line: '964884269'

Test #8:

score: 0

Accepted

time: 2ms

memory: 5256kb

input:

11 13

output:

729153057

result:

ok single line: '729153057'

Test #9:

score: 0

Accepted

time: 19ms

memory: 6228kb

input:

200000 200000

output:

803771125

result:

ok single line: '803771125'

Test #10:

score: 0

Accepted

time: 1ms

memory: 5428kb

input:

199999 562

output:

865836540

result:

ok single line: '865836540'

Test #11:

score: 0

Accepted

time: 11ms

memory: 9636kb

input:

3539 189423

output:

530738158

result:

ok single line: '530738158'

Test #12:

score: 0

Accepted

time: 10ms

memory: 6096kb

input:

198324 173852

output:

963717515

result:

ok single line: '963717515'

Test #13:

score: 0

Accepted

time: 2ms

memory: 5336kb

input:

1 1

output:

result:

ok single line: '3'

Test #14:

score: 0

Accepted

time: 86ms

memory: 12064kb

input:

1000000 1000000

output:

800590912

result:

ok single line: '800590912'

Test #15:

score: 0

Accepted

time: 67ms

memory: 11920kb

input:

5034 999999

output:

946555033

result:

ok single line: '946555033'

Test #16:

score: 0

Accepted

time: 2ms

memory: 5400kb

input:

999998 2042

output:

713878368

result:

ok single line: '713878368'