fork download
copy 
  1. #include<cassert>
  2. #include<cstdio>
  3. #include<tuple>
  4. using namespace std;
  5. typedef long long ll;
  6.  
  7. struct mat2{
  8.     ll a, b, c, d;
  9.     mat2(const ll &a=0, const ll &b=0, const ll &c=0, const ll &d=0): a(a), b(b), c(c), d(d){}
  10.     mat2 operator *(const mat2 &B) const{
  11.         return mat2(a*B.a+b*B.c, a*B.b+b*B.d, c*B.a+d*B.c, c*B.b+d*B.d);
  12.     }
  13.     mat2 operator %(const ll &p) const{
  14.         return mat2(a%p, b%p, c%p, d%p);
  15.     }
  16. };
  17.  
  18. mat2 pow(const mat2 &A, const ll &p, ll n){
  19.     if(n == 1){
  20.         return A;
  21.     }
  22.     mat2 B = pow(A, p, n/2);
  23.     B = B*B%p;
  24.     if(n%2){
  25.         B = A*B%p;
  26.     }
  27.     return B;
  28. }
  29.  
  30. tuple<int, int, int> extgcd(const int &a0, const int &b0){
  31.     ll a=a0, b=b0, p=1, q=0, r=0, s=1;
  32.     while(b){
  33.         ll k = a/b;
  34.         tie(p, r) = make_pair(r, ((p-k*r)%b0+b0)%b0);
  35.         tie(q, s) = make_pair(s, ((q-k*s)%a0+a0)%a0);
  36.         tie(a, b) = make_pair(b, a%b);
  37.     }
  38.     return make_tuple((int)a, (int)p, (int)q);
  39. }
  40.  
  41. int mod_inv(int a, int n){
  42.     tuple<int, int, int> t = extgcd(a, n);
  43.     assert(get<0>(t) == 1);
  44.     return get<1>(t);
  45. }
  46.  
  47. int main(){
  48.     ll b, c, n, p, q;
  49.     scanf("%lld%lld%lld%lld%lld", &b, &c, &n, &p, &q);
  50.     mat2 A(c%p, b%p, 1, 0);
  51.     A = pow(A, p, n);
  52.     ll x = (A.a+A.b)%p;
  53.     if(x == 0){
  54.         puts("-1");
  55.         return 0;
  56.     }
  57.     ll xinv = mod_inv((int)x, p)%q;
  58.     A = mat2(c%q, b%q, 1, 0);
  59.     A = pow(A, q, n);
  60.     ll y = (A.c+A.d)%q;
  61.     printf("%lld\n", xinv*y%q);
  62.     return 0;
  63. }
  64.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
3 4 2 5 7
stdout
copy 
0
https://ideone.com/PIv8N5
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!