QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#50808#959. Multiple?CrysflyAC ✓1033ms3724kbC++112.3kb2022-09-29 14:35:302022-09-29 14:35:32

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-29 14:35:32]
  • 评测
  • 测评结果:AC
  • 用时:1033ms
  • 内存:3724kb
  • [2022-09-29 14:35:30]
  • 提交

answer

#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define mod 998244353
struct modint{
    int x;
    modint(int o=0){x=o;}
    modint &operator = (int o){return x=o,*this;}
    modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
    modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
    modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
    modint &operator ^=(int b){
        modint a=*this,c=1;
        for(;b;b>>=1,a*=a)if(b&1)c*=a;
        return x=c.x,*this;
    }
    modint &operator /=(modint o){return *this *=o^=mod-2;}
    modint &operator +=(int o){return x=x+o>=mod?x+o-mod:x+o,*this;}
    modint &operator -=(int o){return x=x-o<0?x-o+mod:x-o,*this;}
    modint &operator *=(int o){return x=1ll*x*o%mod,*this;}
    modint &operator /=(int o){return *this *= ((modint(o))^=mod-2);}
    template<class I>friend modint operator +(modint a,I b){return a+=b;}
    template<class I>friend modint operator -(modint a,I b){return a-=b;}
    template<class I>friend modint operator *(modint a,I b){return a*=b;}
    template<class I>friend modint operator /(modint a,I b){return a/=b;}
    friend modint operator ^(modint a,int b){return a^=b;}
    friend bool operator ==(modint a,int b){return a.x==b;}
    friend bool operator !=(modint a,int b){return a.x!=b;}
    bool operator ! () {return !x;}
    modint operator - () {return x?mod-x:0;}
};

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 100005
#define inf 0x3f3f3f3f

//ABCDEFHKL
//x    x?,
//x x ?x? 

int n,k;
int phi(int n){
	int res=1;
	For(i,2,n/i)
		if(n%i==0){
			res*=i-1; n/=i;
			while(n%i==0)n/=i,res*=i;
		}
	if(n>1)res*=n-1;
	return res;
}
modint C(int n,int m){
	modint x=1,y=1;
	For(i,1,m)y*=i,x*=(n-i+1);
	return x/y;
} 

signed main()
{
	n=read(),k=read();
	modint res=C(n-1,k-1)*phi(n);
	cout<<res.x;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

input:

9 2

output:

48

result:

ok 1 number(s): "48"

Test #3:

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

input:

222222222 222222

output:

851798824

result:

ok 1 number(s): "851798824"

Test #4:

score: 0
Accepted
time: 1033ms
memory: 3672kb

input:

998244352 249561088

output:

100663296

result:

ok 1 number(s): "100663296"

Test #5:

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

input:

62 3

output:

54900

result:

ok 1 number(s): "54900"

Test #6:

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

input:

328 42

output:

9805666

result:

ok 1 number(s): "9805666"

Test #7:

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

input:

318 67

output:

603200201

result:

ok 1 number(s): "603200201"

Test #8:

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

input:

1368 16

output:

105422469

result:

ok 1 number(s): "105422469"

Test #9:

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

input:

50715 7550

output:

618459631

result:

ok 1 number(s): "618459631"

Test #10:

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

input:

76973 14799

output:

468374999

result:

ok 1 number(s): "468374999"

Test #11:

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

input:

99380 19487

output:

687640903

result:

ok 1 number(s): "687640903"

Test #12:

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

input:

21790 2731

output:

101785330

result:

ok 1 number(s): "101785330"

Test #13:

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

input:

690640 123082

output:

867724310

result:

ok 1 number(s): "867724310"

Test #14:

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

input:

491216 62882

output:

359870082

result:

ok 1 number(s): "359870082"

Test #15:

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

input:

331430 27658

output:

336996189

result:

ok 1 number(s): "336996189"

Test #16:

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

input:

171644 19051

output:

291982732

result:

ok 1 number(s): "291982732"

Test #17:

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

input:

4480506 212264

output:

613147340

result:

ok 1 number(s): "613147340"

Test #18:

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

input:

436959 48003

output:

451377650

result:

ok 1 number(s): "451377650"

Test #19:

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

input:

6393409 1221473

output:

573934740

result:

ok 1 number(s): "573934740"

Test #20:

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

input:

7381276 607288

output:

895895324

result:

ok 1 number(s): "895895324"

Test #21:

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

input:

7951897 1124478

output:

9197219

result:

ok 1 number(s): "9197219"

Test #22:

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

input:

10822617 1773938

output:

200848469

result:

ok 1 number(s): "200848469"

Test #23:

score: 0
Accepted
time: 6ms
memory: 3500kb

input:

13693337 1629029

output:

390448867

result:

ok 1 number(s): "390448867"

Test #24:

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

input:

21596632 5162607

output:

286800922

result:

ok 1 number(s): "286800922"

Test #25:

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

input:

483262472 68378363

output:

805389870

result:

ok 1 number(s): "805389870"

Test #26:

score: 0
Accepted
time: 321ms
memory: 3692kb

input:

504666092 76509085

output:

487083023

result:

ok 1 number(s): "487083023"

Test #27:

score: 0
Accepted
time: 352ms
memory: 3524kb

input:

828059612 83073089

output:

328505426

result:

ok 1 number(s): "328505426"

Test #28:

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

input:

153208783 10166904

output:

109080048

result:

ok 1 number(s): "109080048"

Test #29:

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

input:

476602303 67863017

output:

414678607

result:

ok 1 number(s): "414678607"

Test #30:

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

input:

498005923 42023403

output:

754443127

result:

ok 1 number(s): "754443127"

Test #31:

score: 0
Accepted
time: 99ms
memory: 3632kb

input:

125144994 23866191

output:

754831055

result:

ok 1 number(s): "754831055"

Test #32:

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

input:

146548614 4304228

output:

655902521

result:

ok 1 number(s): "655902521"