gcd-lcm.md

Euclid's Division algorithm

int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}

stl : __gcd(x,y)

Time Complexity: gcd in worst case requires as much steps as fibonacci sequence
It is worst when x=F[n],y=F[n-1]. Time : O(log min(a,b))

Extended Euclid's Algorithm

int extgcd(int a,int b,int &x,int &y){
      if(b==0){
          x=1;
          y=0;
          return a;
      }
      int x1,y1;
      int g = extgcd(b,a%b,x1,y1);
      x = y1;
      y = x1 - y1*(a/b);
      return g;
}

Practise Problems:

• https://codeforces.com/contest/1900/problem/D [Divisors, GCD, Sieve]