QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#89290 | #5817. 小学生数学题 | cyl001 | 100 ✓ | 411ms | 107156kb | C++14 | 720b | 2023-03-19 15:54:06 | 2023-03-19 15:54:09 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 2e7 + 5,p = 998244353;
int n,k,tot,sum,fac,mi[N],pr[N];
bool f[N];
int ksm(int x,int y)
{
int ret = 1;
while(y)
{
if(y & 1) ret = 1LL * ret * x % p;
x = 1LL * x * x % p;
y >>= 1;
}
return ret;
}
int main()
{
scanf("%d%d",&n,&k);
fac = mi[1] = sum = 1;
for(int i = 2;i <= n;i++)
{
fac = 1LL * fac * i % p;
if(!f[i])
{
mi[i] = ksm(i,p - 1 - k);
pr[++tot] = i;
}
sum = (sum + 1LL * fac * mi[i] % p) % p;
for(int j = 1;j <= tot && pr[j] * i <= n;j++)
{
mi[i * pr[j]] = 1LL * mi[i] * mi[pr[j]] % p;
f[i * pr[j]] = 1;
if(i % pr[j] == 0) break;
}
}
printf("%d\n",sum);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 192ms
memory: 56336kb
input:
9450395 1
output:
688545438
result:
ok single line: '688545438'
Test #2:
score: 10
Accepted
time: 187ms
memory: 55396kb
input:
8978812 1
output:
334565356
result:
ok single line: '334565356'
Test #3:
score: 10
Accepted
time: 186ms
memory: 56112kb
input:
8944235 1
output:
982802915
result:
ok single line: '982802915'
Test #4:
score: 10
Accepted
time: 140ms
memory: 46868kb
input:
7081118 3
output:
599009773
result:
ok single line: '599009773'
Test #5:
score: 10
Accepted
time: 162ms
memory: 48344kb
input:
7904241 3
output:
871243720
result:
ok single line: '871243720'
Test #6:
score: 10
Accepted
time: 198ms
memory: 55264kb
input:
9921275 3
output:
549818101
result:
ok single line: '549818101'
Test #7:
score: 10
Accepted
time: 374ms
memory: 96160kb
input:
17575748 14135489
output:
69236780
result:
ok single line: '69236780'
Test #8:
score: 10
Accepted
time: 411ms
memory: 107156kb
input:
19858362 14822524
output:
239890381
result:
ok single line: '239890381'
Test #9:
score: 10
Accepted
time: 398ms
memory: 101676kb
input:
18848696 15530895
output:
88125041
result:
ok single line: '88125041'
Test #10:
score: 10
Accepted
time: 395ms
memory: 96544kb
input:
17787945 13890407
output:
989967864
result:
ok single line: '989967864'
Extra Test:
score: 0
Extra Test Passed