QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #288272 | #5817. 小学生数学题 | Haoyue_06432 | 100 ✓ | 787ms | 189544kb | C++14 | 1.0kb | 2023-12-22 13:14:22 | 2023-12-22 13:14:22 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define maxn 20000005
#define inf 1e18
#define mod 998244353
using namespace std;
ll n,m,ans1=1,inv[maxn],zs[maxn],cnt,ans;
bool bj[maxn];
ll ksm(ll x,ll y)
{
ll ans=1;
while(y)
{
if(y%2==1)ans=(ans*x)%mod;
x=(x*x)%mod;
y/=2;
}
return ans;
}
int main()
{
cin>>n>>m;
inv[1]=1;
for(int i=2;i<=n;i++)
{
if(!bj[i])
{
bj[i]=true;
inv[i]=ksm(ksm(i,m),mod-2);
// cout<<i<<" ";
zs[++cnt]=i;
}
for(int j=1;j<=cnt&&zs[j]*i<=n;j++)
{
bj[zs[j]*i]=true;
inv[zs[j]*i]=(inv[zs[j]]*inv[i])%mod;
// cout<<zs[j]*i<<" ";
}
}
for(int i=1;i<=n;i++)
{
ans1=(ans1*i)%mod;
ans=(ans+ans1*inv[i]%mod)%mod;
}
cout<<ans;
return 0;
}
/*
2 3 6 4 8 12 5 10 15 20 7 14 21 28 35 9 18 27 36 45 63 11 22 33 44 55 77 99 13 26 39 52 65 91 16 32 48 64 80 17 34 51 68 85 19 38 57 76 95 23 46 69 92 24 48 72 96 25 50 75 100 29 58 87 30 60 90 31 62 93 37 74 40 80 41 82 42 84 43 86 47 94 49 98 53 54 56 59 61 66 67 70 71 73 78 79 81 83 88 89 97 523011929
*/
詳細信息
Test #1:
score: 10
Accepted
time: 273ms
memory: 95992kb
input:
9450395 1
output:
688545438
result:
ok single line: '688545438'
Test #2:
score: 10
Accepted
time: 264ms
memory: 90816kb
input:
8978812 1
output:
334565356
result:
ok single line: '334565356'
Test #3:
score: 10
Accepted
time: 257ms
memory: 91640kb
input:
8944235 1
output:
982802915
result:
ok single line: '982802915'
Test #4:
score: 10
Accepted
time: 203ms
memory: 75060kb
input:
7081118 3
output:
599009773
result:
ok single line: '599009773'
Test #5:
score: 10
Accepted
time: 229ms
memory: 80752kb
input:
7904241 3
output:
871243720
result:
ok single line: '871243720'
Test #6:
score: 10
Accepted
time: 313ms
memory: 99448kb
input:
9921275 3
output:
549818101
result:
ok single line: '549818101'
Test #7:
score: 10
Accepted
time: 673ms
memory: 170300kb
input:
17575748 14135489
output:
69236780
result:
ok single line: '69236780'
Test #8:
score: 10
Accepted
time: 787ms
memory: 189544kb
input:
19858362 14822524
output:
239890381
result:
ok single line: '239890381'
Test #9:
score: 10
Accepted
time: 721ms
memory: 183052kb
input:
18848696 15530895
output:
88125041
result:
ok single line: '88125041'
Test #10:
score: 10
Accepted
time: 690ms
memory: 171792kb
input:
17787945 13890407
output:
989967864
result:
ok single line: '989967864'
Extra Test:
score: 0
Extra Test Passed