fork(31) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 20;
  4. long long GCD(long long a, long long b) { return (b == 0) ? a : GCD(b, a % b); }
  5. inline long long LCM(long long a, long long b) { return a / GCD(a, b) * b; }
  6. inline long long normalize(long long x, long long mod) { x %= mod; if (x < 0) x += mod; return x; }
  7. struct GCD_type { long long x, y, d; };
  8. GCD_type ex_GCD(long long a, long long b)
  9. {
  10.     if (b == 0) return {1, 0, a};
  11.     GCD_type pom = ex_GCD(b, a % b);
  12.     return {pom.y, pom.x - a / b * pom.y, pom.d};
  13. }
  14. int testCases;
  15. int t;
  16. long long a[N], n[N], ans, lcm;
  17. int main()
  18. {
  19.     ios_base::sync_with_stdio(0);
  20.     cin.tie(0);
  21.     cin >> t;
  22.     for(int i = 1; i <= t; i++) cin >> a[i] >> n[i], normalize(a[i], n[i]);
  23.     ans = a[1];
  24.     lcm = n[1];
  25.     for(int i = 2; i <= t; i++)
  26.     {
  27.         auto pom = ex_GCD(lcm, n[i]);
  28.         int x1 = pom.x;
  29.         int d = pom.d;
  30.         if((a[i] - ans) % d != 0) return cerr << "No solutions" << endl, 0;
  31.         ans = normalize(ans + x1 * (a[i] - ans) / d % (n[i] / d) * lcm, lcm * n[i] / d);
  32.         lcm = LCM(lcm, n[i]); // you can save time by replacing above lcm * n[i] /d by lcm = lcm * n[i] / d
  33.     }
  34.     cout << ans << " " << lcm << endl;
  35.  
  36.     return 0;
  37. }
  38.  
Success #stdin #stdout 0s 4460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
https://ideone.com/4VodS8
language:
C++14 (gcc 8.3)
created:
6 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!