Advertisement
BaoJIaoPisu

Untitled

Aug 27th, 2021
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.45 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long lt(long long a,long long b,long long p)
  4. {
  5.     long long tam;
  6.     if(b<=0) return 1;
  7.     if(b==1) return a%p;
  8.     tam=lt(a,b/2,p)%p;
  9.     if(b%2==1) return ((tam*tam)%p*a)%p;
  10.     return (tam*tam)%p;
  11. }
  12. int main()
  13. {
  14.     long long x,tam2,n,p,r,i,tam,d;
  15.     cin >> n >> p >> r;
  16.     if(r==0) {
  17.         if(n<=2) {cout << "-1 -1"; return 0;}
  18.         if(p==2) {
  19.             if(n%2==1) if(n>3) {cout << "2 1"; return 0;}
  20.             if(n%2==0) if(n>=4) {cout << "2 1"; return 0;}
  21.         cout << "3 1";
  22.         return 0;
  23.         }
  24.         if(n>=p) {cout << "2 1"; return 0;}
  25.         tam=1;
  26.         for(i=1;i<=n;i++) {
  27.             tam*=i;
  28.             tam%=p;
  29.         }
  30.         if(tam==0) {cout << "3 1"; return 0;}
  31.         else {
  32.             if(__gcd(p,tam)==-1) {cout << "-1 -1"; return 0;}
  33.             d=__gcd(p,tam); p/=d;
  34.             if(p<n) {cout << p+1 << " " << p; return 0;}
  35.         }
  36.         cout << "-1 -1";
  37.         return 0;
  38.     }
  39.     if(n>=2*p) {cout << "-1 -1"; return 0;}
  40.     tam=1;
  41.     for(i=1;i<=n;i++) {
  42.         if(i!=p) {
  43.         tam*=i;
  44.         tam%=p;
  45.         }
  46.     }
  47.     x=lt(tam,p-2,p)%p;
  48.     tam2=x%p;
  49.     if(n>=p) {
  50.          x=r*x%p;
  51.          x%=p;
  52.         cout << p << " " << x; return 0;
  53.     }
  54.     else {
  55.         for(i=2;i<=n;i++) {
  56.              x=i%p*r%p*tam2%p;
  57.              if(x<i) {cout << i << " " << x; return 0;}
  58.         }
  59.     }
  60.     cout << "-1 -1";
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement