QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#781939 | #9553. The Hermit | einekleine18 | WA | 69ms | 31164kb | C++20 | 1.5kb | 2024-11-25 18:06:12 | 2024-11-25 18:06:12 |
Judging History
answer
#include<bits/stdc++.h>
#include <vector>
#define int long long
using a2=std::array<int,2>;
constexpr int mod=998244353,N=1e5+5;
int fac[N],inv[N];
int fp(int a,int b){
int res=1;
while(b){
if(b&1) res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}
void init(){
fac[0]=1;
for(int i=1;i<N;++i){
fac[i]=fac[i-1]*i%mod;
}
inv[N-1]=fp(fac[N-1],mod-2);
for(int i=N-2;i>=0;--i){
inv[i]=inv[i+1]*(i+1)%mod;
}
}
int C(int a,int b){
if(a<b) return 0;
return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
void solve(){
init();
int m,n;
std::cin>>m>>n;
int res=C(m,n)*n%mod;
std::vector<std::map<int,int>>mp(m+1);
for(int i=1;i<=m;++i){
int nums=m/i;
for(auto &[len,cnt]:mp[i]){
res=(res-C(nums-1,len-1)*cnt%mod)%mod;
res=(res+mod)%mod;
if(len==1) continue;
for(int j=i+i;j<=m;j+=i){
mp[j][len-1]+=1;
}
}
res=(res-C(nums-1,n-1))%mod;
res=(res+mod)%mod;
for(int j=i+i;j<=m;j+=i){
mp[j][n-1]+=1;
}
}
std::cout<<res<<'\n';
}
signed main(){
#ifdef LOCAL
std::freopen("in.txt","r",stdin);
std::freopen("out.txt","w",stdout);
#endif
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int _=1;
// std::cin>>_;
for(int i=0;i<_;++i){
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5124kb
input:
4 3
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 2ms
memory: 5156kb
input:
11 4
output:
1187
result:
ok 1 number(s): "1187"
Test #3:
score: 0
Accepted
time: 61ms
memory: 31164kb
input:
100000 99999
output:
17356471
result:
ok 1 number(s): "17356471"
Test #4:
score: 0
Accepted
time: 7ms
memory: 7572kb
input:
11451 1919
output:
845616153
result:
ok 1 number(s): "845616153"
Test #5:
score: -100
Wrong Answer
time: 69ms
memory: 30692kb
input:
99998 12345
output:
663351750
result:
wrong answer 1st numbers differ - expected: '936396560', found: '663351750'