Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- long long lt(long long a,long long b,long long p)
- {
- long long tam;
- if(b<=0) return 1;
- if(b==1) return a%p;
- tam=lt(a,b/2,p)%p;
- if(b%2==1) return ((tam*tam)%p*a)%p;
- return (tam*tam)%p;
- }
- int main()
- {
- long long x,tam2,n,p,r,i,tam,d;
- cin >> n >> p >> r;
- if(r==0) {
- if(n<=2) {cout << "-1 -1"; return 0;}
- if(p==2) {
- if(n%2==1) if(n>3) {cout << "2 1"; return 0;}
- if(n%2==0) if(n>=4) {cout << "2 1"; return 0;}
- cout << "3 1";
- return 0;
- }
- if(n>=p) {cout << "2 1"; return 0;}
- tam=1;
- for(i=1;i<=n;i++) {
- tam*=i;
- tam%=p;
- }
- if(tam==0) {cout << "3 1"; return 0;}
- else {
- if(__gcd(p,tam)==-1) {cout << "-1 -1"; return 0;}
- d=__gcd(p,tam); p/=d;
- if(p<n) {cout << p+1 << " " << p; return 0;}
- }
- cout << "-1 -1";
- return 0;
- }
- if(n>=2*p) {cout << "-1 -1"; return 0;}
- tam=1;
- for(i=1;i<=n;i++) {
- if(i!=p) {
- tam*=i;
- tam%=p;
- }
- }
- x=lt(tam,p-2,p)%p;
- tam2=x%p;
- if(n>=p) {
- x=r*x%p;
- x%=p;
- cout << p << " " << x; return 0;
- }
- else {
- for(i=2;i<=n;i++) {
- x=i%p*r%p*tam2%p;
- if(x<i) {cout << i << " " << x; return 0;}
- }
- }
- cout << "-1 -1";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement