"""
Zadatak 1: Napisati algoritam koji nalazi najveci zajednicki delilac dva prirodna broja.

resenje: Euklidovog algoritma za nalazenje NZD-a dva prirodna broja.
"""
def NZD(a, b):
 
    if b == 0 : 
        return a
            
    nzd = NZD(b, a % b)
    
    return nzd



"""
Zadatak 2: Napisati algoritam kojim se racunaju najveci zajednicki delilac dva prirodna broja i celi brojevi x i y takvi da je ax+by=NZD(a, b).

resenje: obrnuti Euklidov algoritam
"""
def NZD_prosireni(a, b):
 
    if b == 0 : 
        return a, 1, 0
            
    nzd, x1, y1 = NZD_prosireni(b, a % b)
    
    # azuriraju se vrednosti x i y, u startnom momentu su1 i 0
    # primetimo da se ovo azuriranje vrsi nakon rekurzivnog poziva
    x = y1
    y = x1 - (a//b) * y1
    
    return nzd, x, y



"""
Zadatak 3: Napisati algoritam kojim se racuna NZD datog niza prirodnih brojeva.

resenje: koristimo cinjenicu da je NZD(a_1, a_2, ..., a_n)=NZD(NZD(a_1, a_2, ..., a_{n-1}), a_n)
"""
def NZD_niza(l):
    
    nzd = l[0]
 
    for i in range(1, len(l)):
         nzd = NZD(nzd, l[i])

    return nzd
    

 
"""
Zadatak 4: Napisati algoritam kojim se racuna najmanji zajednicki sadrzalac dva prirodna broja.

resenje: koristimo cinjenicu da je a*b=NZD(a,b)*NZS(a,b)
"""
def NZS(a,b):
    return (a* b) / NZD(a,b)



"""
Zadatak 4: Napisati algoritam kojim se racuna NZS datog niza prirodnih brojeva.

resenje: koristimo cinjenicu da je NZS(a_1, a_2, ..., a_n)=NZS(NZS(a_1, a_2, ..., a_{n-1}), a_n)
"""
def NZS_niza(l):
    
    nzs = l[0]
 
    for i in range(1, len(l)):
         nzs = NZS(nzs, l[i])

    return nzs



"""
Zadatak 5: Pronaci NZD-a dva prirodna broja a i b, pri cemu je 0 <= a <= 10^12 i 0 <= b < 10^250.
 
Primetimo broj b moze biti jako veliki prirodan broj (moze prevazici velicinu long long int tipa podataka), pa stoga mora biti zapisan u obliku stringa.
npr. za ulaz a = 1221 i b="1234567891011121314151617181920212223242526272829", izlaz je 3.


resenje: Napisacemo pomocnu funkciju za nalazenje ostatka broja b po modulu a.
 Broj b je dat u obliku stringa, tj. nizom svojih cifara "b_0 b_1 b_2 ... b_n", to zapravo znaci da je b=b_0*10^n + b_1*10^{n-1} + ...+ b_{n-1}*10 + b_n,
 sto mozemo zapisati kao b= 10(...(10(10(10 b_0 + b_1) + b_2) + b_3)...)+ b_n.
 Koristicemo cinjenicu da je (x+y) mod z = (x mod z) + (y mod z).
"""
def redukcijaB(a, b) :
     
    mod = 0

    for i in range(0, len(b)) :
        mod = (mod * 10 + ord(b[i])) % a
 
    return mod

def NZD_veliki(a, b) :
     
    num = redukcijaB(a, b)

    return NZD(a, num)

"""
Zadatak 6: Za dati prirodan broj n odrediti broj parova (a, b), gde je 0 <= a <= n i 0 <= b < n, takvih da je NZD(a, b)=b.

 npr. za ulaz n=2, izlaz je 3
      parovi su: (1, 1), (2, 2) i (2, 1)

      za ulaz n=3, izlaz je 5
      parovi su: (1, 1) (2, 2) (3, 3) (2, 1) i (3, 1)

resenje: Cinjenica da je NZD(a, b)=b, znaci da je b faktor od a. Naivan pristup bi bio da je trazeni broj parova jednak sumi svih delitelja brojeva 1, 2, ..., n.
Efikasniji pristup: za svaki broj b iz skupa {1,2,...,n} brojimo koliko je umnozaka od b koji su manji ili jednaki n, takvih umnozaka ima [n/b].

Kako odrediti koliko ima brojeva b takvih da je [n/b]=k, za neko fiksirano k?
Vazi da je k <= n/b <= k+1, pa je n/(k+1) <= b <= n/k, tj. [n/(k+1)] < b <= [n/k]. Dakle, trazenih brojeva b ima [n/k]-[n/(k+1)] i svi ovakvi brojevi su uzastopni.
npr. za n=5 i k=1 brojevi b bi bili iz skupa {3,4,5}, i ima ih ukupno ima 3=[5/1]-[5/(1+1)]
"""
# uvozimo biblioteku math zbog funkcije floor
import math

def BrojanjeParova(n):
     
    # prvi kandidat za k
    k = n
 
    # za k=n, kako je [n/1]=n, vazi da je minimalno b za k=n jednako 1
    bmin = 1
 
    rezultat = 0
 
    while(bmin <= n):
 
        # maksimalno b za dato k je [n/k]
        bmax = math.floor(n / k)
 
        # dodajemo na ukupan broj parova k * (broj brojeva b takvih da je [n/b]=k)
        rezultat = rezultat + k * (bmax - bmin + 1)
 
        bmin = bmax + 1
        k = math.floor(n / bmin)

    return rezultat