QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#232713 | #959. Multiple? | AlienCollapsar | TL | 24ms | 3396kb | C++14 | 536b | 2023-10-30 20:29:56 | 2023-10-30 20:29:57 |
Judging History
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