fork download
copy 
  1. #include <iostream>
  2.  
  3. struct pair {
  4.  
  5.        long x, 
  6.             y;  
  7.  
  8.        pair(long _x, long _y): x(_x), y(_y) {}
  9. };
  10.  
  11. pair euclid_extended(long a, long b) {
  12.  
  13.      pair prev(1,0); 
  14.      pair curr(0,1);
  15.  
  16.      long q, r;
  17.  
  18.      while(b) {
  19.  
  20.        q = a / b;
  21.        r = a % b;
  22.  
  23.        pair old = curr;
  24.  
  25.        curr.x = prev.x - q * curr.x;
  26.        curr.y = prev.y - q * curr.y;
  27.  
  28.        prev = old;
  29.  
  30.        a = b;
  31.        b = r;  
  32.      }       
  33.  
  34.      return prev; 
  35.  
  36. };
  37.  
  38.  
  39. int main(int argc, char *argv[]) {
  40.  
  41.     //std::ifstream fin(FIN); 
  42.     //std::ofstream fout(FOUT); 
  43.  
  44.     unsigned long a, 
  45.                   n;
  46.  
  47.     std::cin>>a>>n; 
  48.  
  49.     pair sol = euclid_extended(a, n);
  50.  
  51.     std::cout << ((sol.x > 0) ? (sol.x) : (n + sol.x));
  52.  
  53.  
  54.  return(0);
  55.  
  56. }
Success #stdin #stdout 0.01s 5288KB
comments ()
stdin
copy 
5 7
stdout
copy 
3
https://ideone.com/IDFTYn
Invers modular
language:
C++ (gcc 8.3)
created:
53 days 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!