fork download
copy 
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <iostream>
  6. #include <algorithm>
  7. using namespace std;
  8.  
  9. // For Ideone
  10. typedef long long __int64;
  11.  
  12. const int base = 1000;
  13. const int digit = 3;
  14.  
  15. class bign
  16. {
  17. private:
  18.     int _arr[110];
  19.     int _m;
  20.     void _simplify (void);
  21. public:
  22.     bign (void);
  23.     bign (int init);
  24.     friend istream& operator >> (istream& fin, bign& a);
  25.     friend bign operator / (bign a, int b);
  26.     friend int operator % (bign a, int b);
  27.     friend bool operator == (bign a, bign b);
  28. };
  29. void bign::_simplify (void)
  30. {
  31.     for (int i = 0; i <= _m; i++)
  32.     {
  33.         if (i == _m && _arr[i] >= base) _m++;
  34.         _arr[i + 1] += _arr[i] / base;
  35.         _arr[i] %= base;
  36.     }
  37. }
  38. bign::bign (void) : _m(0) { memset(_arr, 0, sizeof(_arr)); }
  39. bign::bign (int init) : _m(0)
  40. {
  41.     memset(_arr, 0, sizeof(_arr));
  42.     _arr[0] = init;
  43.     _simplify();
  44. }
  45. istream& operator >> (istream& fin, bign& a)
  46. {
  47.     char init[10010]; int len, b, t;
  48.     fin >> init;
  49.     len = strlen(init); a._m = -1;
  50.     for (int i = len - 1; i >= 0;)
  51.     {
  52.         t = 0, b = 1;
  53.         for (int j = 0; j < digit && i >= 0; j++, i--)
  54.         {
  55.             t += (init[i] - '0') * b;
  56.             b *= 10;
  57.         }
  58.         a._arr[++a._m] = t;
  59.     }
  60.     return fin;
  61. }
  62. bign operator / (bign a, int b)
  63. {
  64.     for (int i = a._m; i >= 0; i--)
  65.     {
  66.         if (a._arr[i] < b && i == a._m && i != 0) a._m--;
  67.         if (i > 0) a._arr[i - 1] += (a._arr[i] % b) * base;
  68.         a._arr[i] /= b;
  69.     } return a;
  70. }
  71. int operator % (bign a, int b)
  72. {
  73.     for (int i = a._m; i >= 0; i--)
  74.     {
  75.         if (i == 0) return a._arr[i] % b;
  76.         else a._arr[i - 1] += (a._arr[i] % b) * base;
  77.     }
  78. }
  79. bool operator == (bign a, bign b)
  80. {
  81.     if (a._m != b._m) return false;
  82.     for (int i = 0; i <= a._m; i++)
  83.         if (a._arr[i] != b._arr[i]) return false;
  84.     return true;
  85. }
  86.  
  87. int cha_a[110], cha_b[110];
  88. int hm[510], hk[510], rm, rk, bs[510], md[510];
  89. struct rec 
  90. {
  91.     __int64 gcd, crdx, crdy;
  92.     rec (void) {}
  93.     rec (__int64 g0, __int64 cx0, __int64 cy0) : gcd(g0), crdx(cx0), crdy(cy0) {}
  94. };
  95. rec euclid (__int64 x, __int64 y)
  96. {
  97.     if (y == 0) return rec(x, 1, 0);
  98.     else
  99.     {
  100.         rec ans = euclid(y, x % y);
  101.         return rec(ans.gcd, ans.crdy, ans.crdx - (x / y) * ans.crdy);
  102.     }
  103. }
  104. pair<int, int> trans (int *cha, int hhm, int hhk)
  105. {
  106.     int round = 0, cnt = 0, p = hhm;
  107.     while (1)
  108.     {
  109.         if (p == hhk) break;
  110.         else if (cnt && p == hhm) { cnt = -1; break; }
  111.         p = cha[p], ++cnt;
  112.     }
  113.     if (cnt == -1) return make_pair(-1, 0);
  114.     while (1)
  115.     {
  116.         if (round && p == hhk) break;
  117.         p = cha[p], ++round;
  118.     } return make_pair(cnt, round);
  119. }
  120.  
  121. int main ()
  122. {
  123.     bign m, k; int d; __int64 lm, lb, z;
  124.     while (1)
  125.     {
  126.         restart: cin >> d;
  127.         if (d == -1) break;
  128.         for (int i = 1; i < d; i++) cin >> cha_a[i];
  129.         for (int i = 0; i < d; i++) cin >> cha_b[i];
  130.         cin >> m >> k;
  131.         for (rm = 0; !(m == 0); rm++)
  132.         {
  133.             hm[rm] = m % d;
  134.             m = m / d;
  135.         }
  136.         for (rk = 0; !(k == 0); rk++)
  137.         {
  138.             hk[rk] = k % d;
  139.             k = k / d;
  140.         }
  141.         if (rm != rk) { printf("NO\n"); goto restart; }
  142.         for (int i = 0; i < rm - 1; i++)
  143.         {
  144.             pair<int, int> adp = trans(cha_b, hm[i], hk[i]);
  145.             if (adp.first == -1) { printf("NO\n"); goto restart; }
  146.             else md[i] = adp.first, bs[i] = adp.second;
  147.         }
  148.         pair<int, int> adp = trans(cha_a, hm[rm - 1], hk[rm - 1]);
  149.         if (adp.first == -1) { printf("NO\n"); goto restart; }
  150.         else md[rm - 1] = adp.first, bs[rm - 1] = adp.second;
  151.         lm = 0, lb = 1;
  152.         for (int i = 0; i < rm; i++)
  153.         {
  154.             rec adp = euclid(lb, bs[i]);
  155.             if ((lm - md[i]) % adp.gcd) { printf("NO\n"); goto restart; }
  156.             z = adp.crdy * ((lm - md[i]) / adp.gcd);
  157.             lb = lb / adp.gcd * bs[i];
  158.             lm = z * bs[i] + md[i];
  159.             lm = ((lm % lb) + lb) % lb;
  160.         }
  161.         // FOR POJ Submittion, please use: 
  162.         //      printf("%I64d\n", lm);
  163.         printf("%lld\n", lm);
  164.     } 
  165.     return 0;
  166. }
  167.  
stdin
copy 
2
1
1 0
4
7
2
1
0 1
100
200
-1
compilation info 
prog.cpp: In function ‘int operator%(bign, int)’:
prog.cpp:78: warning: control reaches end of non-void function
stdout
copy 
1
NO
https://ideone.com/RJCWR
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
secret

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!