QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#54000#959. Multiple?tricyzhkxAC ✓1047ms3724kbC++14552b2022-10-06 16:04:222022-10-06 16:04:25

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-06 16:04:25]
  • 评测
  • 测评结果:AC
  • 用时:1047ms
  • 内存:3724kb
  • [2022-10-06 16:04:22]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
const int mod=998244353;
typedef long long ll;
ll power(ll a,int b)
{
	ll ans=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1) ans=ans*a%mod;
	return ans;
}
int phi(int n)
{
	int ans=n;
	for(int i=2;i*i<=n;i++)
		if(n%i==0)
		{
			ans=ans/i*(i-1);
			for(;n%i==0;n/=i);
		}
	if(n>1) ans=ans/n*(n-1);
	return ans;
}
int main()
{
	int n,k,dw=1,fac=1;
	cin>>n>>k;
	for(int i=1;i<=k-1;i++) dw=(ll)dw*(n-i)%mod,fac=(ll)fac*i%mod;
	cout<<dw*power(fac,mod-2)%mod*phi(n)%mod<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3444kb

input:

4 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3444kb

input:

9 2

output:

48

result:

ok 1 number(s): "48"

Test #3:

score: 0
Accepted
time: 3ms
memory: 3684kb

input:

222222222 222222

output:

851798824

result:

ok 1 number(s): "851798824"

Test #4:

score: 0
Accepted
time: 1047ms
memory: 3640kb

input:

998244352 249561088

output:

100663296

result:

ok 1 number(s): "100663296"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

62 3

output:

54900

result:

ok 1 number(s): "54900"

Test #6:

score: 0
Accepted
time: 2ms
memory: 3696kb

input:

328 42

output:

9805666

result:

ok 1 number(s): "9805666"

Test #7:

score: 0
Accepted
time: 2ms
memory: 3508kb

input:

318 67

output:

603200201

result:

ok 1 number(s): "603200201"

Test #8:

score: 0
Accepted
time: 1ms
memory: 3656kb

input:

1368 16

output:

105422469

result:

ok 1 number(s): "105422469"

Test #9:

score: 0
Accepted
time: 2ms
memory: 3676kb

input:

50715 7550

output:

618459631

result:

ok 1 number(s): "618459631"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

76973 14799

output:

468374999

result:

ok 1 number(s): "468374999"

Test #11:

score: 0
Accepted
time: 2ms
memory: 3680kb

input:

99380 19487

output:

687640903

result:

ok 1 number(s): "687640903"

Test #12:

score: 0
Accepted
time: 2ms
memory: 3644kb

input:

21790 2731

output:

101785330

result:

ok 1 number(s): "101785330"

Test #13:

score: 0
Accepted
time: 1ms
memory: 3588kb

input:

690640 123082

output:

867724310

result:

ok 1 number(s): "867724310"

Test #14:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

491216 62882

output:

359870082

result:

ok 1 number(s): "359870082"

Test #15:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

331430 27658

output:

336996189

result:

ok 1 number(s): "336996189"

Test #16:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

171644 19051

output:

291982732

result:

ok 1 number(s): "291982732"

Test #17:

score: 0
Accepted
time: 3ms
memory: 3656kb

input:

4480506 212264

output:

613147340

result:

ok 1 number(s): "613147340"

Test #18:

score: 0
Accepted
time: 2ms
memory: 3556kb

input:

436959 48003

output:

451377650

result:

ok 1 number(s): "451377650"

Test #19:

score: 0
Accepted
time: 3ms
memory: 3580kb

input:

6393409 1221473

output:

573934740

result:

ok 1 number(s): "573934740"

Test #20:

score: 0
Accepted
time: 4ms
memory: 3576kb

input:

7381276 607288

output:

895895324

result:

ok 1 number(s): "895895324"

Test #21:

score: 0
Accepted
time: 3ms
memory: 3580kb

input:

7951897 1124478

output:

9197219

result:

ok 1 number(s): "9197219"

Test #22:

score: 0
Accepted
time: 9ms
memory: 3580kb

input:

10822617 1773938

output:

200848469

result:

ok 1 number(s): "200848469"

Test #23:

score: 0
Accepted
time: 9ms
memory: 3512kb

input:

13693337 1629029

output:

390448867

result:

ok 1 number(s): "390448867"

Test #24:

score: 0
Accepted
time: 24ms
memory: 3568kb

input:

21596632 5162607

output:

286800922

result:

ok 1 number(s): "286800922"

Test #25:

score: 0
Accepted
time: 283ms
memory: 3516kb

input:

483262472 68378363

output:

805389870

result:

ok 1 number(s): "805389870"

Test #26:

score: 0
Accepted
time: 315ms
memory: 3516kb

input:

504666092 76509085

output:

487083023

result:

ok 1 number(s): "487083023"

Test #27:

score: 0
Accepted
time: 342ms
memory: 3684kb

input:

828059612 83073089

output:

328505426

result:

ok 1 number(s): "328505426"

Test #28:

score: 0
Accepted
time: 39ms
memory: 3564kb

input:

153208783 10166904

output:

109080048

result:

ok 1 number(s): "109080048"

Test #29:

score: 0
Accepted
time: 276ms
memory: 3576kb

input:

476602303 67863017

output:

414678607

result:

ok 1 number(s): "414678607"

Test #30:

score: 0
Accepted
time: 170ms
memory: 3576kb

input:

498005923 42023403

output:

754443127

result:

ok 1 number(s): "754443127"

Test #31:

score: 0
Accepted
time: 96ms
memory: 3520kb

input:

125144994 23866191

output:

754831055

result:

ok 1 number(s): "754831055"

Test #32:

score: 0
Accepted
time: 20ms
memory: 3588kb

input:

146548614 4304228

output:

655902521

result:

ok 1 number(s): "655902521"