QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#381434#3063. Faulty FactorialI_Love_Sonechka#AC ✓379ms199028kbC++141.3kb2024-04-07 17:42:582024-04-07 17:42:59

Judging History

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

  • [2024-04-07 17:42:59]
  • 评测
  • 测评结果:AC
  • 用时:379ms
  • 内存:199028kb
  • [2024-04-07 17:42:58]
  • 提交

answer

#include <bits/stdc++.h>
#include <math.h>
			
using namespace std;

// c++ short types
#define Int long long
#define vt vector

int mod;
int mul(int a, int b) {
	return (a * 1ll * b) % mod;
}

const int nmax = 2 * 1e7 + 1;
int inv[nmax], fact[nmax], suff[nmax];

void solver() {
	Int n;
	int p, r;
	cin >> n >> p >> r;
	mod = p;
	if(n >= 2 * p) {
		if(r == 0) {
			cout << p << " " << p-1 << "\n";
		} else {
			cout << "-1 -1\n";
		}
		return ;
	}
	inv[1] = 1;
	for(int a = 2; a < min(p, nmax); ++a) {
		inv[a] = p - (long long)(p/a) * inv[p % a] % p; 
	}
	fact[0] = 1;
	for(int i = 1; i <= n; ++i) {
		fact[i] = mul(fact[i-1], i);
	}
	suff[n+1] = 1;
	suff[n] = n % p;
	for(int i = n-1; i >= 0; --i) {
		suff[i] = mul(i, suff[i+1]);
	}
	for(int i = 2; i <= n; ++i) {
		int val = mul(fact[i-1], suff[i+1]);
		if(val == 0) {
			if(r == 0) {
				cout << i << " " << i-1 << "\n";
				return ;
			} else {
				continue;
			}
		}
		assert(val >= 0 && val < p);
		int d = mul(r, inv[val]);
		if(1 <= d && d < i) {
			cout << i << " " << d << endl;
			return ;
		}
	}
	cout << "-1 -1\n";
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int tt = 1;
	for(int t = 0; t < tt; ++t) {
    solver();
	}
	return 0;
}

詳細信息

Test #1:

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

input:

4 5 1

output:

3 2

result:

ok Correct!

Test #2:

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

input:

4 127 24

output:

-1 -1

result:

ok Correct!

Test #3:

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

input:

2 2 0

output:

-1 -1

result:

ok Correct!

Test #4:

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

input:

2 2 1

output:

2 1

result:

ok Correct!

Test #5:

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

input:

3 2 0

output:

3 2

result:

ok Correct!

Test #6:

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

input:

3 2 1

output:

2 1

result:

ok Correct!

Test #7:

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

input:

4 2 0

output:

2 1

result:

ok Correct!

Test #8:

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

input:

4 2 1

output:

-1 -1

result:

ok Correct!

Test #9:

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

input:

1000000000000000000 2 0

output:

2 1

result:

ok Correct!

Test #10:

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

input:

1000000000000000000 2 1

output:

-1 -1

result:

ok Correct!

Test #11:

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

input:

2 3 0

output:

-1 -1

result:

ok Correct!

Test #12:

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

input:

2 3 2

output:

-1 -1

result:

ok Correct!

Test #13:

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

input:

2 3 1

output:

2 1

result:

ok Correct!

Test #14:

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

input:

3 3 0

output:

2 1

result:

ok Correct!

Test #15:

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

input:

3 3 2

output:

3 1

result:

ok Correct!

Test #16:

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

input:

5 3 0

output:

2 1

result:

ok Correct!

Test #17:

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

input:

5 3 1

output:

3 1

result:

ok Correct!

Test #18:

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

input:

6 3 0

output:

3 2

result:

ok Correct!

Test #19:

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

input:

6 3 1

output:

-1 -1

result:

ok Correct!

Test #20:

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

input:

1000000000000000000 3 0

output:

3 2

result:

ok Correct!

Test #21:

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

input:

1000000000000000000 3 2

output:

-1 -1

result:

ok Correct!

Test #22:

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

input:

2 7 0

output:

-1 -1

result:

ok Correct!

Test #23:

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

input:

2 7 4

output:

-1 -1

result:

ok Correct!

Test #24:

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

input:

6 7 0

output:

-1 -1

result:

ok Correct!

Test #25:

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

input:

6 7 3

output:

2 1

result:

ok Correct!

Test #26:

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

input:

7 7 0

output:

2 1

result:

ok Correct!

Test #27:

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

input:

7 7 3

output:

7 4

result:

ok Correct!

Test #28:

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

input:

7 7 1

output:

7 6

result:

ok Correct!

Test #29:

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

input:

13 7 0

output:

2 1

result:

ok Correct!

Test #30:

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

input:

13 7 3

output:

7 3

result:

ok Correct!

Test #31:

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

input:

14 7 0

output:

7 6

result:

ok Correct!

Test #32:

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

input:

14 7 1

output:

-1 -1

result:

ok Correct!

Test #33:

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

input:

1000000000000000000 7 0

output:

7 6

result:

ok Correct!

Test #34:

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

input:

1000000000000000000 7 5

output:

-1 -1

result:

ok Correct!

Test #35:

score: 0
Accepted
time: 32ms
memory: 22976kb

input:

2 4937129 0

output:

-1 -1

result:

ok Correct!

Test #36:

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

input:

2 4937129 1249280

output:

-1 -1

result:

ok Correct!

Test #37:

score: 0
Accepted
time: 168ms
memory: 61456kb

input:

4937128 4937129 0

output:

-1 -1

result:

ok Correct!

Test #38:

score: 0
Accepted
time: 91ms
memory: 61600kb

input:

4937128 4937129 4041807

output:

4031 1683

result:

ok Correct!

Test #39:

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

input:

4937129 4937129 0

output:

2 1

result:

ok Correct!

Test #40:

score: 0
Accepted
time: 98ms
memory: 61468kb

input:

4937129 4937129 3844991

output:

4937129 1092138

result:

ok Correct!

Test #41:

score: 0
Accepted
time: 127ms
memory: 82928kb

input:

7675468 4937129 0

output:

2 1

result:

ok Correct!

Test #42:

score: 0
Accepted
time: 141ms
memory: 82872kb

input:

7675468 4937129 3435996

output:

4937129 214360

result:

ok Correct!

Test #43:

score: 0
Accepted
time: 149ms
memory: 100036kb

input:

9874257 4937129 0

output:

2 1

result:

ok Correct!

Test #44:

score: 0
Accepted
time: 187ms
memory: 101028kb

input:

9874257 4937129 4502081

output:

4937129 4502081

result:

ok Correct!

Test #45:

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

input:

9874258 4937129 0

output:

4937129 4937128

result:

ok Correct!

Test #46:

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

input:

9874258 4937129 136077

output:

-1 -1

result:

ok Correct!

Test #47:

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

input:

1000000000000000000 4937129 0

output:

4937129 4937128

result:

ok Correct!

Test #48:

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

input:

1000000000000000000 4937129 600783

output:

-1 -1

result:

ok Correct!

Test #49:

score: 0
Accepted
time: 55ms
memory: 44044kb

input:

2 9999991 0

output:

-1 -1

result:

ok Correct!

Test #50:

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

input:

2 9999991 3547763

output:

-1 -1

result:

ok Correct!

Test #51:

score: 0
Accepted
time: 370ms
memory: 122812kb

input:

9999990 9999991 0

output:

-1 -1

result:

ok Correct!

Test #52:

score: 0
Accepted
time: 180ms
memory: 121168kb

input:

9999990 9999991 6305202

output:

3283 3204

result:

ok Correct!

Test #53:

score: 0
Accepted
time: 168ms
memory: 122044kb

input:

9999991 9999991 0

output:

2 1

result:

ok Correct!

Test #54:

score: 0
Accepted
time: 216ms
memory: 122900kb

input:

9999991 9999991 3290391

output:

9999991 6709600

result:

ok Correct!

Test #55:

score: 0
Accepted
time: 253ms
memory: 161560kb

input:

15088677 9999991 0

output:

2 1

result:

ok Correct!

Test #56:

score: 0
Accepted
time: 280ms
memory: 162180kb

input:

15088677 9999991 3238851

output:

9999991 8892695

result:

ok Correct!

Test #57:

score: 0
Accepted
time: 327ms
memory: 198988kb

input:

19999981 9999991 0

output:

2 1

result:

ok Correct!

Test #58:

score: 0
Accepted
time: 356ms
memory: 199028kb

input:

19999981 9999991 1114448

output:

9999991 1114448

result:

ok Correct!

Test #59:

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

input:

19999982 9999991 0

output:

9999991 9999990

result:

ok Correct!

Test #60:

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

input:

19999982 9999991 1468197

output:

-1 -1

result:

ok Correct!

Test #61:

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

input:

1000000000000000000 9999991 0

output:

9999991 9999990

result:

ok Correct!

Test #62:

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

input:

1000000000000000000 9999991 5561940

output:

-1 -1

result:

ok Correct!

Test #63:

score: 0
Accepted
time: 87ms
memory: 65476kb

input:

2924166 9732533 6303282

output:

7418 6575

result:

ok Correct!

Test #64:

score: 0
Accepted
time: 78ms
memory: 54492kb

input:

3133068 6687881 5091931

output:

51475 53

result:

ok Correct!

Test #65:

score: 0
Accepted
time: 158ms
memory: 105820kb

input:

8103430 9897059 6793055

output:

6741 1009

result:

ok Correct!

Test #66:

score: 0
Accepted
time: 117ms
memory: 76584kb

input:

5608852 7464623 4135409

output:

4004 827

result:

ok Correct!

Test #67:

score: 0
Accepted
time: 94ms
memory: 71384kb

input:

5399319 6048071 5880044

output:

4142 2871

result:

ok Correct!

Test #68:

score: 0
Accepted
time: 145ms
memory: 97792kb

input:

7602001 8561963 8429820

output:

10566 763

result:

ok Correct!

Test #69:

score: 0
Accepted
time: 93ms
memory: 67840kb

input:

4168376 7768193 5120738

output:

3271 2855

result:

ok Correct!

Test #70:

score: 0
Accepted
time: 45ms
memory: 32792kb

input:

1712124 3894673 1570469

output:

6665 6648

result:

ok Correct!

Test #71:

score: 0
Accepted
time: 89ms
memory: 67764kb

input:

4658359 6914419 1388646

output:

2768 755

result:

ok Correct!

Test #72:

score: 0
Accepted
time: 41ms
memory: 25152kb

input:

1780103 1889131 641681

output:

3524 2999

result:

ok Correct!

Test #73:

score: 0
Accepted
time: 379ms
memory: 121660kb

input:

9999978 9999991 7955288

output:

-1 -1

result:

ok Correct!

Test #74:

score: 0
Accepted
time: 289ms
memory: 121924kb

input:

9999974 9999991 7469222

output:

4999996 1

result:

ok Correct!

Test #75:

score: 0
Accepted
time: 277ms
memory: 121996kb

input:

9999976 9999991 3692550

output:

4999996 4999995

result:

ok Correct!