QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#343551#3063. Faulty FactorialPetroTarnavskyi#AC ✓133ms3704kbC++201.5kb2024-03-02 18:42:512024-03-02 18:42:52

Judging History

This is the latest submission verdict.

  • [2024-03-02 18:42:52]
  • Judged
  • Verdict: AC
  • Time: 133ms
  • Memory: 3704kb
  • [2024-03-02 18:42:51]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

int mult(int a, int b, int mod)
{
	return (LL)a * b % mod;
}
int binpow(int a, int n, int mod)
{
	int res = 1;
	while(n)
	{
		if(n & 1)
			res = mult(res, a, mod);
		a = mult(a, a, mod);
		n /= 2;
	}
	return res;
}

PII solve()
{
	LL n, p, r;
	cin >> n >> p >> r;	
	if(n >= 2 * p)
	{
		if(r != 0)
			return {-1, -1};
		else
			return {p, p - 1};
	}
	if(n >= p)
	{
		if(r != 0)
		{
			LL ost = 1;
			FOR(i, 1, n + 1)
				if(i != p)
					ost = mult(ost, i, p);
			assert(ost != 0);
			ost = mult(r, binpow(ost, p - 2, p), p);
			
			return {p, ost};
		}
		else
		{
			if(n > p)
				return {p + 1, p};
			if(p == 2)
				return {-1, -1};
			return {2, 1};
		}
	}
	//n < p
	if(r == 0)
		return {-1, -1};
	int ifact = 1;
	FOR(i, 1, n + 1)
		ifact = mult(ifact, i, p);
	ifact = binpow(ifact, p - 2, p);
	
	FOR(i, 1, n + 1)
	{
		int nval = mult(i, ifact, p);
		nval = mult(nval, r, p);
		
		if(nval < i)
			return {i, nval};
	}
	return {-1, -1};
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	auto ans = solve();
	cout << ans.F << " " << ans.S << "\n";
	
	
	
	return 0;
}




Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3568kb

input:

4 5 1

output:

3 2

result:

ok Correct!

Test #2:

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

input:

4 127 24

output:

-1 -1

result:

ok Correct!

Test #3:

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

input:

2 2 0

output:

-1 -1

result:

ok Correct!

Test #4:

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

input:

2 2 1

output:

2 1

result:

ok Correct!

Test #5:

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

input:

3 2 0

output:

3 2

result:

ok Correct!

Test #6:

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

input:

3 2 1

output:

2 1

result:

ok Correct!

Test #7:

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

input:

4 2 0

output:

2 1

result:

ok Correct!

Test #8:

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

input:

4 2 1

output:

-1 -1

result:

ok Correct!

Test #9:

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

input:

1000000000000000000 2 0

output:

2 1

result:

ok Correct!

Test #10:

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

input:

1000000000000000000 2 1

output:

-1 -1

result:

ok Correct!

Test #11:

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

input:

2 3 0

output:

-1 -1

result:

ok Correct!

Test #12:

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

input:

2 3 2

output:

-1 -1

result:

ok Correct!

Test #13:

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

input:

2 3 1

output:

2 1

result:

ok Correct!

Test #14:

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

input:

3 3 0

output:

2 1

result:

ok Correct!

Test #15:

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

input:

3 3 2

output:

3 1

result:

ok Correct!

Test #16:

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

input:

5 3 0

output:

4 3

result:

ok Correct!

Test #17:

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

input:

5 3 1

output:

3 1

result:

ok Correct!

Test #18:

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

input:

6 3 0

output:

3 2

result:

ok Correct!

Test #19:

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

input:

6 3 1

output:

-1 -1

result:

ok Correct!

Test #20:

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

input:

1000000000000000000 3 0

output:

3 2

result:

ok Correct!

Test #21:

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

input:

1000000000000000000 3 2

output:

-1 -1

result:

ok Correct!

Test #22:

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

input:

2 7 0

output:

-1 -1

result:

ok Correct!

Test #23:

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

input:

2 7 4

output:

-1 -1

result:

ok Correct!

Test #24:

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

input:

6 7 0

output:

-1 -1

result:

ok Correct!

Test #25:

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

input:

6 7 3

output:

2 1

result:

ok Correct!

Test #26:

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

input:

7 7 0

output:

2 1

result:

ok Correct!

Test #27:

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

input:

7 7 3

output:

7 4

result:

ok Correct!

Test #28:

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

input:

7 7 1

output:

7 6

result:

ok Correct!

Test #29:

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

input:

13 7 0

output:

8 7

result:

ok Correct!

Test #30:

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

input:

13 7 3

output:

7 3

result:

ok Correct!

Test #31:

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

input:

14 7 0

output:

7 6

result:

ok Correct!

Test #32:

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

input:

14 7 1

output:

-1 -1

result:

ok Correct!

Test #33:

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

input:

1000000000000000000 7 0

output:

7 6

result:

ok Correct!

Test #34:

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

input:

1000000000000000000 7 5

output:

-1 -1

result:

ok Correct!

Test #35:

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

input:

2 4937129 0

output:

-1 -1

result:

ok Correct!

Test #36:

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

input:

2 4937129 1249280

output:

-1 -1

result:

ok Correct!

Test #37:

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

input:

4937128 4937129 0

output:

-1 -1

result:

ok Correct!

Test #38:

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

input:

4937128 4937129 4041807

output:

4031 1683

result:

ok Correct!

Test #39:

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

input:

4937129 4937129 0

output:

2 1

result:

ok Correct!

Test #40:

score: 0
Accepted
time: 34ms
memory: 3700kb

input:

4937129 4937129 3844991

output:

4937129 1092138

result:

ok Correct!

Test #41:

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

input:

7675468 4937129 0

output:

4937130 4937129

result:

ok Correct!

Test #42:

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

input:

7675468 4937129 3435996

output:

4937129 214360

result:

ok Correct!

Test #43:

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

input:

9874257 4937129 0

output:

4937130 4937129

result:

ok Correct!

Test #44:

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

input:

9874257 4937129 4502081

output:

4937129 4502081

result:

ok Correct!

Test #45:

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

input:

9874258 4937129 0

output:

4937129 4937128

result:

ok Correct!

Test #46:

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

input:

9874258 4937129 136077

output:

-1 -1

result:

ok Correct!

Test #47:

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

input:

1000000000000000000 4937129 0

output:

4937129 4937128

result:

ok Correct!

Test #48:

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

input:

1000000000000000000 4937129 600783

output:

-1 -1

result:

ok Correct!

Test #49:

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

input:

2 9999991 0

output:

-1 -1

result:

ok Correct!

Test #50:

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

input:

2 9999991 3547763

output:

-1 -1

result:

ok Correct!

Test #51:

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

input:

9999990 9999991 0

output:

-1 -1

result:

ok Correct!

Test #52:

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

input:

9999990 9999991 6305202

output:

3283 3204

result:

ok Correct!

Test #53:

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

input:

9999991 9999991 0

output:

2 1

result:

ok Correct!

Test #54:

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

input:

9999991 9999991 3290391

output:

9999991 6709600

result:

ok Correct!

Test #55:

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

input:

15088677 9999991 0

output:

9999992 9999991

result:

ok Correct!

Test #56:

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

input:

15088677 9999991 3238851

output:

9999991 8892695

result:

ok Correct!

Test #57:

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

input:

19999981 9999991 0

output:

9999992 9999991

result:

ok Correct!

Test #58:

score: 0
Accepted
time: 133ms
memory: 3704kb

input:

19999981 9999991 1114448

output:

9999991 1114448

result:

ok Correct!

Test #59:

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

input:

19999982 9999991 0

output:

9999991 9999990

result:

ok Correct!

Test #60:

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

input:

19999982 9999991 1468197

output:

-1 -1

result:

ok Correct!

Test #61:

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

input:

1000000000000000000 9999991 0

output:

9999991 9999990

result:

ok Correct!

Test #62:

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

input:

1000000000000000000 9999991 5561940

output:

-1 -1

result:

ok Correct!

Test #63:

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

input:

2924166 9732533 6303282

output:

7418 6575

result:

ok Correct!

Test #64:

score: 0
Accepted
time: 22ms
memory: 3704kb

input:

3133068 6687881 5091931

output:

51475 53

result:

ok Correct!

Test #65:

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

input:

8103430 9897059 6793055

output:

6741 1009

result:

ok Correct!

Test #66:

score: 0
Accepted
time: 38ms
memory: 3612kb

input:

5608852 7464623 4135409

output:

4004 827

result:

ok Correct!

Test #67:

score: 0
Accepted
time: 37ms
memory: 3624kb

input:

5399319 6048071 5880044

output:

4142 2871

result:

ok Correct!

Test #68:

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

input:

7602001 8561963 8429820

output:

10566 763

result:

ok Correct!

Test #69:

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

input:

4168376 7768193 5120738

output:

3271 2855

result:

ok Correct!

Test #70:

score: 0
Accepted
time: 12ms
memory: 3608kb

input:

1712124 3894673 1570469

output:

6665 6648

result:

ok Correct!

Test #71:

score: 0
Accepted
time: 31ms
memory: 3596kb

input:

4658359 6914419 1388646

output:

2768 755

result:

ok Correct!

Test #72:

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

input:

1780103 1889131 641681

output:

3524 2999

result:

ok Correct!

Test #73:

score: 0
Accepted
time: 125ms
memory: 3612kb

input:

9999978 9999991 7955288

output:

-1 -1

result:

ok Correct!

Test #74:

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

input:

9999974 9999991 7469222

output:

4999996 1

result:

ok Correct!

Test #75:

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

input:

9999976 9999991 3692550

output:

4999996 4999995

result:

ok Correct!