QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #287986 | #5817. 小学生数学题 | Haoyue_06432 | 30 | 322ms | 114240kb | C++14 | 778b | 2023-12-21 13:58:45 | 2023-12-21 13:58:45 |
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],s,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;
s=ksm(i,m);
inv[i]=(mod-mod/s)*inv[mod%s]%mod;
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;
}
zs[++cnt]=i;
}
}
for(int i=1;i<=n;i++)
{
ans1=(ans1*i)%mod;
ans=(ans+ans1*inv[i]%mod)%mod;
}
cout<<ans;
return 0;
}
/*
inv[i]=(mod-mod/i)*inv[mod%i]%mod
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 322ms
memory: 114240kb
input:
9450395 1
output:
688545438
result:
ok single line: '688545438'
Test #2:
score: 10
Accepted
time: 311ms
memory: 108948kb
input:
8978812 1
output:
334565356
result:
ok single line: '334565356'
Test #3:
score: 10
Accepted
time: 286ms
memory: 108500kb
input:
8944235 1
output:
982802915
result:
ok single line: '982802915'
Test #4:
score: 0
Runtime Error
input:
7081118 3
output:
result:
Test #5:
score: 0
Runtime Error
input:
7904241 3
output:
result:
Test #6:
score: 0
Runtime Error
input:
9921275 3
output:
result:
Test #7:
score: 0
Runtime Error
input:
17575748 14135489
output:
result:
Test #8:
score: 0
Runtime Error
input:
19858362 14822524
output:
result:
Test #9:
score: 0
Runtime Error
input:
18848696 15530895
output:
result:
Test #10:
score: 0
Runtime Error
input:
17787945 13890407