allia

быстрый евклид

Sep 12th, 2020
961
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cmath>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int Evklid(int a, int b)
  7. {
  8.   int res=1;
  9.   while (a!=0 && b!=0)
  10.   {
  11.     while (a%2==0 && b%2==0)
  12.     {
  13.        a/=2;
  14.        b/=2;
  15.       res*=2;
  16.     }
  17.     while (a%2==0)
  18.     a/=2;
  19.     while (b%2==0)
  20.     b/=2;
  21.     if (a>=b) a-=b;
  22.     else b-=a;
  23.   }
  24.  
  25.   return res*b;
  26. }
  27. int main()
  28. {
  29.   int a=0, b=0;
  30.   cin >> a >> b;
  31.    cout << Evklid(a, b);
  32.  
  33. }
RAW Paste Data