QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#766604 | #9553. The Hermit | wowlie# | WA | 153ms | 7380kb | C++20 | 1.8kb | 2024-11-20 17:55:49 | 2024-11-20 17:55:52 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
const LL N=100010,mod=998244353;
LL primes[N],minp[N],idx;
bool st[N];
void is_primes(LL n)
{
for(LL i=2;i<=n;i++)
{
if(!st[i])primes[idx++]=i,minp[i]=i;
for(LL j=0;i*primes[j]<=n;j++)
{
st[i*primes[j]]=true;
minp[i*primes[j]]=primes[j];
if(i%primes[j]==0)break;
}
}
}
LL fact[N],infact[N];//fact表示阶乘,infact表示阶乘的逆元
LL qmi(LL a,LL b)
{
LL res=1;
while(b)
{
if(b&1)res=(LL)res*a%mod;
a=(LL)a*a%mod;
b>>=1;
}
return res;
}
void init()
{
fact[0]=infact[0]=1;
for(LL i=1;i<N;i++)
{
fact[i]=(LL)fact[i-1]*i%mod;
infact[i]=(LL)infact[i-1]*qmi(i,mod-2)%mod;
}
}
LL query(LL a,LL b)
{
LL res=(LL)fact[a]*infact[b]%mod*infact[a-b]%mod;
return res;
}
void solve()
{
LL n,m;
cin>>n>>m;
LL res=0;
for(LL i=1;i<=n;i++)
{
map<LL,LL>mp;
for(LL j=i;j<=n;j+=i)
{
LL val=j/i;
while(val!=minp[val]&&val!=1)
{
LL t=minp[val];
mp[t]++;
while(val%t==0)val/=t;
}
if(val!=1)mp[val]++;
}
LL t=0;
if(n/i-1>=m)t=query(n/i-1,m);
for(auto [u,v]:mp)
{
if(v>=m)t=(t-query(v,m)%mod+mod)%mod;
}
res=(res+t*m%mod)%mod;
LL cnt=0;
for(LL j=1;j*j<=i;j++)
{
if(i%j==0)
{
if(j!=i/j)cnt+=2;
else cnt++;
}
}
for(LL j=1;j<=cnt;j++)
{
LL val=0;
if(n/i-1>=m-j)val=query(n/i-1,m-j);
for(auto [u,v]:mp)
{
if(v>=m-j)val=(val-query(v,m-j)%mod+mod)%mod;
}
res=(res+query(cnt,j)*val%mod*(m-j)%mod)%mod;
}
}
cout<<res<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
LL T;
T=1;
init();
is_primes(1e5);
while(T--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 12ms
memory: 6288kb
input:
4 3
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 13ms
memory: 6076kb
input:
11 4
output:
1187
result:
ok 1 number(s): "1187"
Test #3:
score: 0
Accepted
time: 153ms
memory: 7380kb
input:
100000 99999
output:
17356471
result:
ok 1 number(s): "17356471"
Test #4:
score: 0
Accepted
time: 21ms
memory: 6220kb
input:
11451 1919
output:
845616153
result:
ok 1 number(s): "845616153"
Test #5:
score: -100
Wrong Answer
time: 153ms
memory: 6736kb
input:
99998 12345
output:
284096349
result:
wrong answer 1st numbers differ - expected: '936396560', found: '284096349'