QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#232713#959. Multiple?AlienCollapsarTL 24ms3396kbC++14536b2023-10-30 20:29:562023-10-30 20:29:57

Judging History

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

  • [2023-10-30 20:29:57]
  • 评测
  • 测评结果:TL
  • 用时:24ms
  • 内存:3396kb
  • [2023-10-30 20:29:56]
  • 提交

answer

#include<cstdio>
#include<iostream>
using namespace std;
using ll=long long;
const int Mod=998244353;
ll quickly_power(ll a,int b){
	ll res=1;
	for(;b;b>>=1,(a*=a)%=Mod)if(b&1)(res*=a)%=Mod;
	return res;
}
ll phi(int n){
	ll res=1;
	for(int i=2;i*i<=n;++i)if(n%i==0){
		res*=i-1;
		while(n%i==0)res*=i,n/=i;
		res/=i;
	}
	if(n!=1)res*=n-1;
	return res;
}
int main(){
	int n,k;cin>>n>>k;
	ll ans=1;
	for(int i=1;i<k;++i)
		(ans*=(n-i)*quickly_power(i,Mod-2)%Mod)%=Mod;
	cout<<ans*phi(n)%Mod<<'\n';
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3300kb

input:

4 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3396kb

input:

9 2

output:

48

result:

ok 1 number(s): "48"

Test #3:

score: 0
Accepted
time: 24ms
memory: 3376kb

input:

222222222 222222

output:

851798824

result:

ok 1 number(s): "851798824"

Test #4:

score: -100
Time Limit Exceeded

input:

998244352 249561088

output:


result: