QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#33107 | #959. Multiple? | Wu_Ren | WA | 2ms | 3752kb | C++17 | 544b | 2022-05-27 19:49:43 | 2022-05-27 19:49:45 |
Judging History
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'