UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#210189#3789. 我可能是C题drdilyor100557ms1152kbC++111.2kb2024-08-06 09:06:292024-08-06 13:01:26

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
void ts(){cout<<"IAKIOI\n";}
inline int read(){
	int n=0,f=1,ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		n=n*10+ch-'0';
		ch=getchar();
	}
	return n*f;
}
int n,mod,r;
int qkp(int b,int p){
	int r=1;
	while(p){
		if(p&1)(r*=b)%=mod;
		p/=2;
		(b*=b)%=mod;
	}
	return r;
}
signed main(){
	n=read(),mod=read(),r=read();
	if(n>=2*mod){
		if(!r){
			printf("%lld %lld\n",1,n);
		}
		else{printf("-1 -1\n");}
		return 0;
	}
	if(n>=mod){
		int v=1;
		for(int i=1;i<mod;i++)v*=i,v%=mod;
		for(int i=mod+1;i<=n;i++)v*=i,v%=mod;
		if(!r){
			if(mod==2){
				if(n==2){printf("-1 -1\n");}
				else printf("1 3\n");
			}
			else{
				printf("1 2\n");
			}
		}
		else{
			printf("%lld %lld\n",r*qkp(v,mod-2)%mod,mod);
		}
		return 0;
	}
	if(!r){printf("-1 -1\n");return 0;}
	//n<1e7.
	int f=1;
	int xd=qkp(r,mod-2);
	for(int i=1;i<=n;i++)f*=i,f%=mod;
	xd*=f;xd%=mod;
	int cur=0,cur2=0;
	for(int i=1;i<n;i++){
		cur2+=f;
		if(cur2>=mod)cur2-=mod;
		cur+=xd;
		if(cur>=mod)cur-=mod;
		if(i<cur&&cur<=n){
			printf("%lld %lld\n",i,cur);return 0;
		}
		//p/r.
	}
	printf("-1 -1\n");
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 20
Accepted

Test #1:

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

input:

65 9096341 8846419

output:

13 18

result:

ok ok

Test #2:

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

input:

8 1155823 0

output:

-1 -1

result:

ok ok

Test #3:

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

input:

91 79 78

output:

51 79

result:

ok ok

Test #4:

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

input:

34 19 0

output:

1 2

result:

ok ok

Test #5:

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

input:

2 2 0

output:

-1 -1

result:

ok ok

Test #6:

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

input:

100 11 4

output:

-1 -1

result:

ok ok

Test #7:

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

input:

80 37 0

output:

1 80

result:

ok ok

Test #8:

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

input:

69 7498201 1018078

output:

23 36

result:

ok ok

Test #9:

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

input:

67 3825511 2142238

output:

-1 -1

result:

ok ok

Test #10:

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

input:

95 61 53

output:

29 61

result:

ok ok

Subtask #2:

score: 20
Accepted

Test #11:

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

input:

983 6365153 4944288

output:

73 283

result:

ok ok

Test #12:

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

input:

612 3807691 0

output:

-1 -1

result:

ok ok

Test #13:

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

input:

744 727 405

output:

57 727

result:

ok ok

Test #14:

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

input:

209 127 0

output:

1 2

result:

ok ok

Test #15:

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

input:

2 2 0

output:

-1 -1

result:

ok ok

Test #16:

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

input:

900 409 78

output:

-1 -1

result:

ok ok

Test #17:

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

input:

624 293 0

output:

1 624

result:

ok ok

Test #18:

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

input:

741 2421109 2171469

output:

21 22

result:

ok ok

Test #19:

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

input:

791 7968479 5501513

output:

-1 -1

result:

ok ok

Test #20:

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

input:

112 89 31

output:

17 89

result:

ok ok

Subtask #3:

score: 60
Accepted

Test #21:

score: 60
Accepted
time: 134ms
memory: 1152kb

input:

8546661 9551959 3193270

output:

1 188196

result:

ok ok

Test #22:

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

input:

4298159 9302861 0

output:

-1 -1

result:

ok ok

Test #23:

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

input:

513325 422083 392021

output:

259709 422083

result:

ok ok

Test #24:

score: 0
Accepted
time: 26ms
memory: 1136kb

input:

1566540 991871 0

output:

1 2

result:

ok ok

Test #25:

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

input:

2 2 0

output:

-1 -1

result:

ok ok

Test #26:

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

input:

620835803 5180041 4842294

output:

-1 -1

result:

ok ok

Test #27:

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

input:

15765760 5025589 0

output:

1 15765760

result:

ok ok

Test #28:

score: 0
Accepted
time: 69ms
memory: 1152kb

input:

4306335 4916707 2219367

output:

1 3480267

result:

ok ok

Test #29:

score: 0
Accepted
time: 75ms
memory: 1148kb

input:

4843363 9786319 4491526

output:

1 1673950

result:

ok ok

Test #30:

score: 0
Accepted
time: 244ms
memory: 1148kb

input:

15042407 9461099 3361767

output:

5550468 9461099

result:

ok ok

Extra Test:

score: 0
Extra Test Passed