QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#61202#3063. Faulty Factorialchiranko#AC ✓433ms44272kbC++908b2022-11-11 14:47:032022-11-11 14:47:05

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-11 14:47:05]
  • Judged
  • Verdict: AC
  • Time: 433ms
  • Memory: 44272kb
  • [2022-11-11 14:47:03]
  • Submitted

answer

#include<bits/stdc++.h>
#define rep(l,r) for(int i=l;i<=r;i++)
#define jrep(l,r) for(int j=l;j<=r;j++)

using namespace std;

typedef long long ll;
const int N=2e7+10;

ll n;
int p,r;
int inv[N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>p>>r;
	if(n>=p*2)
	{
		if(!r)cout<<p<<' '<<1;
		else cout<<"-1 -1";
		return 0;
	}
	inv[0]=inv[1]=1;
	for(int i=2;i<p;++i)inv[i]=(ll)(p-p/i)*inv[p%i]%p;
	if(n>=p)
	{
		if(!r)
		{
			if(n==p&&p==2)cout<<"-1 -1";
			else if(p==2)cout<<"3 1";
			else cout<<"2 1";
		}
		else
		{
			int now=1;
			rep(1,n)if(i!=p)now=(ll)now*i%p;
			cout<<p<<' '<<(ll)r*inv[now]%p;
		}
		return 0;
	}
	if(!r)
	{
		cout<<"-1 -1";
		return 0;
	}
	int now=1;
	rep(1,n)now=(ll)now*i%p;
	rep(2,n)
	{
		int t=(ll)r*i%p*inv[now]%p;
		if(t<i)
		{
			cout<<i<<' '<<t;
			return 0;
		}
	}
	cout<<"-1 -1";
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3412kb

input:

4 5 1

output:

3 2

result:

ok Correct!

Test #2:

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

input:

4 127 24

output:

-1 -1

result:

ok Correct!

Test #3:

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

input:

2 2 0

output:

-1 -1

result:

ok Correct!

Test #4:

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

input:

2 2 1

output:

2 1

result:

ok Correct!

Test #5:

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

input:

3 2 0

output:

3 1

result:

ok Correct!

Test #6:

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

input:

3 2 1

output:

2 1

result:

ok Correct!

Test #7:

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

input:

4 2 0

output:

2 1

result:

ok Correct!

Test #8:

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

input:

4 2 1

output:

-1 -1

result:

ok Correct!

Test #9:

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

input:

1000000000000000000 2 0

output:

2 1

result:

ok Correct!

Test #10:

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

input:

1000000000000000000 2 1

output:

-1 -1

result:

ok Correct!

Test #11:

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

input:

2 3 0

output:

-1 -1

result:

ok Correct!

Test #12:

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

input:

2 3 2

output:

-1 -1

result:

ok Correct!

Test #13:

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

input:

2 3 1

output:

2 1

result:

ok Correct!

Test #14:

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

input:

3 3 0

output:

2 1

result:

ok Correct!

Test #15:

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

input:

3 3 2

output:

3 1

result:

ok Correct!

Test #16:

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

input:

5 3 0

output:

2 1

result:

ok Correct!

Test #17:

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

input:

5 3 1

output:

3 1

result:

ok Correct!

Test #18:

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

input:

6 3 0

output:

3 1

result:

ok Correct!

Test #19:

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

input:

6 3 1

output:

-1 -1

result:

ok Correct!

Test #20:

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

input:

1000000000000000000 3 0

output:

3 1

result:

ok Correct!

Test #21:

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

input:

1000000000000000000 3 2

output:

-1 -1

result:

ok Correct!

Test #22:

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

input:

2 7 0

output:

-1 -1

result:

ok Correct!

Test #23:

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

input:

2 7 4

output:

-1 -1

result:

ok Correct!

Test #24:

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

input:

6 7 0

output:

-1 -1

result:

ok Correct!

Test #25:

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

input:

6 7 3

output:

2 1

result:

ok Correct!

Test #26:

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

input:

7 7 0

output:

2 1

result:

ok Correct!

Test #27:

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

input:

7 7 3

output:

7 4

result:

ok Correct!

Test #28:

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

input:

7 7 1

output:

7 6

result:

ok Correct!

Test #29:

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

input:

13 7 0

output:

2 1

result:

ok Correct!

Test #30:

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

input:

13 7 3

output:

7 3

result:

ok Correct!

Test #31:

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

input:

14 7 0

output:

7 1

result:

ok Correct!

Test #32:

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

input:

14 7 1

output:

-1 -1

result:

ok Correct!

Test #33:

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

input:

1000000000000000000 7 0

output:

7 1

result:

ok Correct!

Test #34:

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

input:

1000000000000000000 7 5

output:

-1 -1

result:

ok Correct!

Test #35:

score: 0
Accepted
time: 72ms
memory: 22988kb

input:

2 4937129 0

output:

-1 -1

result:

ok Correct!

Test #36:

score: 0
Accepted
time: 65ms
memory: 24452kb

input:

2 4937129 1249280

output:

-1 -1

result:

ok Correct!

Test #37:

score: 0
Accepted
time: 73ms
memory: 23252kb

input:

4937128 4937129 0

output:

-1 -1

result:

ok Correct!

Test #38:

score: 0
Accepted
time: 134ms
memory: 22628kb

input:

4937128 4937129 4041807

output:

4031 1683

result:

ok Correct!

Test #39:

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

input:

4937129 4937129 0

output:

2 1

result:

ok Correct!

Test #40:

score: 0
Accepted
time: 132ms
memory: 23460kb

input:

4937129 4937129 3844991

output:

4937129 1092138

result:

ok Correct!

Test #41:

score: 0
Accepted
time: 65ms
memory: 24184kb

input:

7675468 4937129 0

output:

2 1

result:

ok Correct!

Test #42:

score: 0
Accepted
time: 182ms
memory: 23432kb

input:

7675468 4937129 3435996

output:

4937129 214360

result:

ok Correct!

Test #43:

score: 0
Accepted
time: 64ms
memory: 24608kb

input:

9874257 4937129 0

output:

2 1

result:

ok Correct!

Test #44:

score: 0
Accepted
time: 196ms
memory: 23512kb

input:

9874257 4937129 4502081

output:

4937129 4502081

result:

ok Correct!

Test #45:

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

input:

9874258 4937129 0

output:

4937129 1

result:

ok Correct!

Test #46:

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

input:

9874258 4937129 136077

output:

-1 -1

result:

ok Correct!

Test #47:

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

input:

1000000000000000000 4937129 0

output:

4937129 1

result:

ok Correct!

Test #48:

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

input:

1000000000000000000 4937129 600783

output:

-1 -1

result:

ok Correct!

Test #49:

score: 0
Accepted
time: 132ms
memory: 43392kb

input:

2 9999991 0

output:

-1 -1

result:

ok Correct!

Test #50:

score: 0
Accepted
time: 129ms
memory: 43596kb

input:

2 9999991 3547763

output:

-1 -1

result:

ok Correct!

Test #51:

score: 0
Accepted
time: 138ms
memory: 42840kb

input:

9999990 9999991 0

output:

-1 -1

result:

ok Correct!

Test #52:

score: 0
Accepted
time: 273ms
memory: 42560kb

input:

9999990 9999991 6305202

output:

3283 3204

result:

ok Correct!

Test #53:

score: 0
Accepted
time: 138ms
memory: 44236kb

input:

9999991 9999991 0

output:

2 1

result:

ok Correct!

Test #54:

score: 0
Accepted
time: 259ms
memory: 43676kb

input:

9999991 9999991 3290391

output:

9999991 6709600

result:

ok Correct!

Test #55:

score: 0
Accepted
time: 122ms
memory: 43200kb

input:

15088677 9999991 0

output:

2 1

result:

ok Correct!

Test #56:

score: 0
Accepted
time: 336ms
memory: 43188kb

input:

15088677 9999991 3238851

output:

9999991 8892695

result:

ok Correct!

Test #57:

score: 0
Accepted
time: 138ms
memory: 43132kb

input:

19999981 9999991 0

output:

2 1

result:

ok Correct!

Test #58:

score: 0
Accepted
time: 403ms
memory: 44272kb

input:

19999981 9999991 1114448

output:

9999991 1114448

result:

ok Correct!

Test #59:

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

input:

19999982 9999991 0

output:

9999991 1

result:

ok Correct!

Test #60:

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

input:

19999982 9999991 1468197

output:

-1 -1

result:

ok Correct!

Test #61:

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

input:

1000000000000000000 9999991 0

output:

9999991 1

result:

ok Correct!

Test #62:

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

input:

1000000000000000000 9999991 5561940

output:

-1 -1

result:

ok Correct!

Test #63:

score: 0
Accepted
time: 173ms
memory: 42628kb

input:

2924166 9732533 6303282

output:

7418 6575

result:

ok Correct!

Test #64:

score: 0
Accepted
time: 130ms
memory: 29576kb

input:

3133068 6687881 5091931

output:

51475 53

result:

ok Correct!

Test #65:

score: 0
Accepted
time: 233ms
memory: 43328kb

input:

8103430 9897059 6793055

output:

6741 1009

result:

ok Correct!

Test #66:

score: 0
Accepted
time: 179ms
memory: 34120kb

input:

5608852 7464623 4135409

output:

4004 827

result:

ok Correct!

Test #67:

score: 0
Accepted
time: 143ms
memory: 28656kb

input:

5399319 6048071 5880044

output:

4142 2871

result:

ok Correct!

Test #68:

score: 0
Accepted
time: 222ms
memory: 37540kb

input:

7602001 8561963 8429820

output:

10566 763

result:

ok Correct!

Test #69:

score: 0
Accepted
time: 162ms
memory: 34432kb

input:

4168376 7768193 5120738

output:

3271 2855

result:

ok Correct!

Test #70:

score: 0
Accepted
time: 77ms
memory: 19144kb

input:

1712124 3894673 1570469

output:

6665 6648

result:

ok Correct!

Test #71:

score: 0
Accepted
time: 153ms
memory: 32340kb

input:

4658359 6914419 1388646

output:

2768 755

result:

ok Correct!

Test #72:

score: 0
Accepted
time: 48ms
memory: 12476kb

input:

1780103 1889131 641681

output:

3524 2999

result:

ok Correct!

Test #73:

score: 0
Accepted
time: 433ms
memory: 43160kb

input:

9999978 9999991 7955288

output:

-1 -1

result:

ok Correct!

Test #74:

score: 0
Accepted
time: 344ms
memory: 42840kb

input:

9999974 9999991 7469222

output:

4999996 1

result:

ok Correct!

Test #75:

score: 0
Accepted
time: 358ms
memory: 43436kb

input:

9999976 9999991 3692550

output:

4999996 4999995

result:

ok Correct!