Greatest Common Divisor

Greatest common divisor:
       দুটি সংখ্যা a ও b যদি non-zero হয় তাহলে তাদের gcd হল largest common divisor a ও b হয়।যদি a এবং b non-zero হয় তাহলে,
                      1 ≤ gcd(a, b) ≤ min(|a|)


Gcd function এর কিছু elementary property:

gcd(a, 0)= |a|

gcd(a, ka)=|a|

gcd(0, 0)=0

gcd(an, bn)=n*gcd(a, b) where n ≥ 0

যদি n|ab এবং gcd(a, n)= 1 তাহলে n|b

যদি gcd(a, p) = 1 এবং gcd(b, p) = 1 হয় তাহলে gcd(ab, p) = 1

Euclidian algorithm:
    Euclid algorithm এর যে principal এর উপর কাজ করে তাহলো

       Gcd(a, b) = gcd (b, a%b)

         Base case হল: gcd(a, 0) = a

Algorithm implementation:

আমরা এটি প্রমান করতে পারি। কিন্তু এটি প্রমান করার আগে প্রথমে division theorem সম্পর্কে idea নিতে হবে।

Division theorem:
          যদি a একটি পূর্ণ সংখ্যা ও b একটি ধনাতম্ক পূর্ণ সংখ্যা হয় তাহলে আমরা এমন ২টি unique পূর্ণ সংখ্যা পাব k এবং r যেখানে,
                    a = k*b+r
            যেখানে k = a/b = ভাগফল
                       r = a mod b
     আমরা b|a লিখতে পারি যদি এবং কেবল যদি a mod b = 0 হয়।

Euclid algorithm এর প্রমানঃ

   ধরি, g = gcd(a, b)

         a = k*b+r [k হল k=a/b অধনাত্মক সংখ্যা ও r হল ভাগশেষ।]
যেহেতু g, a কে ভাগ করতে পারে তার মানে g, k*b+r নিঃশেষে ভাগ করতে পারে।

যেহেতু g, b কে নিঃশেষে ভাগ করতে পারে g, k*b কেও নিঃশেষে ভাগ করতে পারে।তার ফলে g r কেও ভাগ করতে পারে, তা না হলে k*b+r, b দ্বারা ভাগ করা যাবে না।

তাহলে আমরা প্রমান করলাম যে, g, b এবং r কে নিঃশেষে ভাগ করতে পারে।

          এখন ধরি,
             g’ = gcd(b, r)

     যেহেতু g’, b ও r উভয় কে নিঃশেষে ভাগ করতে পারে ত্রার মানে এটি k*b+r কে নিঃশেষে ভাগ করতে পারবে।

    তার মানে, g’,a কে নিঃশেষে ভাগ করতে পারবে।

আমরা contradiction এর মাধ্যমে প্রমান করতে 
             পারি যে, g = g’

অর্থাৎ gcd(a, b)= gcd(b, r) = gcd(b, a%b)


 কিছু Property of GCD function:


1) Communicative Law : GCD(a,b) = GCD(b,a)

2) Associative Law : GCD(a,GCD(b,c)) = GCD(GCD(a,b),c) 

3)  GCD(a,b,c) = GCD(GCD(a,b),c) 


Things to remember:

1) GCD(4,-2) returns -2 but correct answer should be 2 . To get the correct value we need to send the absolute value of the inputs to the algorithm or use the absolute value of the return value.

.2) GCD(0,0)=0 but the algo will try to do 0%0 for that we might 

get RTE. We need to take care of this manually.

Common Divisors

Common divisor: 

         যদি  d, a এর একটি divisor হয় এবং d যদি b এর ও একটি divisor হয় তাহলে আমরা বলতে পারি যে d হল a এবং b এর common divisor।

         6 এর divisor হল 1, 2, 3, 6
         12 এর divisor হল 1, 2, 3, 4, 6, 12

         Common divisor (6, 12) = 1, 2, 3, 6

কিছু দরকারি তথ্য common divisor এরঃ

        1)   d | a এবং d | b implies  d | (a+b) এবং d | (a-b)
                         
        আরও সাধারনভাবে বলা যায় যে, d | a এবং d | b implies d | (ax+by) [সকল x এবং y এর জন্য] এবং যদি  a|b তবে,|a|≤|b| অথবা b=0

        2)  Number of Common Divisor(a, b) = Number Of Divisor (gcd(a, b))

             প্রমানঃ

             GCD(24, 30) = 6
             অর্থাৎ 24 এবং 30 এর মধ্যে এমন কোনো common divisor      নেই যা 6 এর চেয়ে বড়। 6 এর divisor হল 1, 2, 3, and 6।  24, 30     এর জন্য 6 এর চেয়ে ছোট বা সমান কোনো সংখ্যা নেই যা 24, 30     কে ভাগ করতে পারে এবং{1, 2, 3, 6} এর সেটে এ পরে না।

Problem : COMDIV - Number of common divisors

Editorial : Editorial Link

        বাংলায় প্রোগ্রামিং রিসোর্সসমূহ

LINK

List of algorithmic problems uva

Topological Sorts using indegree (Kahn's algorithm)

Tutorial - Kahn's Algorithm for Topological Sorting
             
                Shafaetsplanet

                Tutorial


ALGORITHM:


The usual algorithms for topological sorting have running time linear in the number of nodes plus the number of edges, asymptotically, ${\displaystyle O(\left|{V}\right|+\left|{E}\right|)}$.

Implementation:

Basic Number Theory Tutorial in Bangla by ইকরাম মাহমুদ

Tutorial Link - progkriya

Love for programming

Number of common divisors of 2 numbers

Problem link: COMDIV - Number of common divisors

For this we need to know
                         CommonDivisor(a,b) = NumberOf Divisor(gcd(a,b)) proof

Find the number of divisors: Time Complexity O(sqrt(n))

tutorial for finding the number of divisors : progkriya

Solution:

Codeforces problem B Two Buttons analysis

Problem Type : BFS , math , greedy , shortest path

Problem link: Two Buttons

this was a very interesting for me.

This problem asks us what is the minimum steps we need to reach from one given number to another given number by multiplying by 2 or  subtracting 1

i have found 2 ways to solve this problem 
       1) using bfs (hard way)
       2) simple mathematics

The hard way:

let us try to analyze 2 given test cases 

1)  4 ->6  minimum steps: 2
2) 10 ->1 minimum steps: 9

let us make a graph using the 2 test cases

UVA 383 - Shipping Routes analysis

Problem Type : Single-Source Shortest Paths On Unweighted Graph  (BFS/DFS)

Its a basic SSSP problem.

"The cost of a shipment is equal to the size of the shipment times the number of shipping legs required times $100."

we just have to do a bfs or dfs from given source if we have't done bfs or dfs on the source before.We can get the cost of the shipment using the above statement using the cost of the destination :D

UVA 260 - Il Gioco dell'X analysis

Problem Type : Finding Connected Components (BFS/DFS)

Let us try to understand the problem

"The game ‘Il Gioco dell’ X’ is played on a N by N board (N ≥ 2). The object of both players, say Black and White, is to join opposite sides of the board by placing in turn their pawns on the board in such a way that a path is made from one side to the other by adjacent (neighboring) pawns of their own color."

Though the statement is not very clear how Black and White will win but we can get the idea from the given picture