QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#33107#959. Multiple?Wu_RenWA 2ms3752kbC++17544b2022-05-27 19:49:432022-05-27 19:49:45

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-27 19:49:45]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3752kb
  • [2022-05-27 19:49:43]
  • 提交

answer

#include <bits/stdc++.h>
const int mod=998244353;
using namespace std;
int n,K;
int ksm(int a,int k){
	int res=1;
	for(;k;k>>=1,a=1ll*a*a%mod) if(k&1) res=1ll*res*a%mod;
	return res;
}
int main(){
	scanf("%d%d",&n,&K);
	int tp=n,res=1;
	n--,K--;
	for(int i=2;i*i<=n;i++) if(tp%i==0){
		tp/=i,res*=(i-1);
		while(tp%i==0) tp/=i,res*=i;
	}
	if(tp>1) res*=(tp-1);
	for(int i=0;i<K;i++) res=1ll*res*(n-i)%mod;
	int ifac=1;
	for(int i=1;i<=K;i++) ifac=1ll*ifac*i%mod;
	ifac=ksm(ifac,mod-2);
	printf("%d\n",1ll*res*ifac%mod);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 3752kb

input:

4 1

output:

3

result:

wrong answer 1st numbers differ - expected: '2', found: '3'