NT Part 1:GCD, LCM, Euclidean Algorithm

The definitions of GCD and LCM are well-known, (and taught in middle school I think) I will skip the definitions.

Also, since $\text{lcm} (a,b) \cdot \text{gcd} (a,b) = ab$ , calculating GCD is equivalent to calculating LCM.
Now, how do we calculate the GCD of two numbers?

A naive solution would be iterating over all positive integers no more than $\text{min} (a,b)$ .
This will get the GCD in $O(\text{min}(a,b))$ , very very slow.

We can calculate the GCD of $a,b$ in $O(\log ab)$ using Euclidean Algorithm.
This algorithm uses the easy-to-prove fact $\text{gcd}(a,b) = \text{gcd} (b, r)$ , where $r$ is the remainder when $a$ is divided by $b$ , or just a%b.

We can now use the following code.

#include <iostream>
using namespace std;
int gcd(int u, int v)
{
    return u%v==0?v:gcd(v,u%v);
}
int main(void)
{
    int x, y;
    cin>>x>>y;
    cout<<gcd(x,y);
}

How do we prove that this algorithm is $O(\log ab)$ ? Well, let's suppose that we started with $(a,b)$ .
Then, we go to $(b,r)$ , where $r$ is defined similarly as above. It can be proved that $br < \frac{1}{2}ab$ .
Therefore, the product of two numbers in the function decreases by half every time. Done!

Here's a challenge. Can we find the numbers $x, y$ such that $ux+vy=\text{gcd} (u,v)$ ?
There exists infinitely many pairs - this is Bezout's Lemma. The algorithm to generate such pairs is called Extended Euclidean Algorithm.

Comments

Breaking The Summation Formula (Part 1)

Q. f ( n ) = - 1 + 2 - 3 + .. + ( - 1) n n . Given n, find out f(n) Approach(1)- Bruteforce: 1. Calculation sum=n*(n+1)/2 2. loop[i=1,i=n : i+=2] odd+=i 3.ans=sum-2*odd Code: #include < bits / stdc ++. h > using namespace std ; int main (){ long long x ; cin >> x ; long long p =( x *( x + 1 ))/ 2 ; long long bad = 0 ; for ( long long i = 1 ; i <= x ; i += 2 ) bad += i ; cout << p - 2 * bad << endl ; } Approach(2)-Greedy: Basic: s=1+2+3+4+....+n Formula: sum=n*(n+1)/2= (n/2) + (n+1).2 ...

Game Theory with examples

Game Theory with examples Introduction In this article I will be covering problems related to two players game in which it is assumed that both players play optimally and we have to find out the winner of the game. First we will look at the basic division of positions to winning and losing . Then we will see the Game of Nim and then see how it will be used to solve the Composite games . Basic Division of positions to winning and losing Problem Statement: Consider a simple game played by two players A and B . There are n stones on the table. Each player can pick 1 , 2 or 5 stones in each turn. Both players pick the stones alternately until the total number of stones left on the table is 0. The player unable to make the move will lose. Assuming that both the players play optimally, output the winner of the game. Solution: As you can see positions 1 , 2 and 5 are winning positions since the player can pick up all the stones and other player will n...

বিগেনার কম্পিটিটিভ প্রোগ্রামরদের জন্য কিছু প্রয়োজনীয় টপিকস

Competitive Programming For Beginners Topics Subtopics Time/Memory Complexity 1. Importance of calculating time/memory complexity and how to do it Basic STL (C++) 1. Vector ( insert , erase , iteration ) 2. Queue 3. Stack 4. Deque Data Structure 1. Map (C++) 2. Priority Queue (C++) 3. Set (C++) 4. Linked list using array Bitwise Operation 1. Bitwise operation (AND , OR , XOR and more) 2. Manipulation of bits 3. Some special use Math 1.Calculating GCD efficiently (Euclidean algorithm) 2.Sieve (finding prime numbers) 3.Bitwise sieve 4. Factorization 5. Modular Arithmetic ( addition , multiplication , calculating bigmod) 6. Fermat's little theorem and its use 7. Totient function 8. Combinatorics (factorials , counting problem) Sorting Algorithm 1. Bubble sort 2. Insertion sort 3. Counting sort 4. Selection sort 5. Quick sort 6. Merge sort Recursion 1. Introduction to recursion 2. Backtracking Gre...

This lifeless coder is welcoming you!

Search This Blog