# Least Greatest (500 points)
## Description
Today in Santa's course in Introduction to Algorithms, Santa told us about the greatest common divisor and the least common multiple.He this gave the following problem as homework and I don't know how to solve it.Can you please help me with it?
Target: nc challs.xmas.htsp.ro 6050
Authors: Gabies, Nutu
## Solution
```shell$ nc challs.xmas.htsp.ro 6050Hey, you there! You look like you know your way with complex alogrithms.There's this weird task that I can't get my head around. It goes something like this:Given two numbers g and l, tell me how many pairs of numbers (x, y) exist such that gcd(x, y) = g and lcm(x, y) = lAlso, i have to answer 100 such questions in at most 90 seconds.
Test number: 1/100gcd(x, y) = 87641lcm(x, y) = 750862998151937487679256930365054379979841```
I found a ready-made function for the same task: [link](https://www.geeksforgeeks.org/given-gcd-g-lcm-l-find-number-possible-pairs-b/). But this code gave errors on 3-4 tests. It was only necessary to add a second slash to divide large integers. Here is the finished code:
```pythonfrom pwn import *
conn = remote('challs.xmas.htsp.ro', 6050)
def totalPrimeFactors(n):      count = 0;  
    if ((n % 2) == 0):          count += 1;          while ((n % 2) == 0):              n //= 2;       i = 3;     while (i * i <= n):          if ((n % i) == 0):              count += 1;              while ((n % i) == 0):                  n //= i;          i += 2; 
    if (n > 2):          count += 1;       return count;   def countPairs(G, L):      if (L % G != 0):          return 0;       div = int(L // G);  
    return (1 << totalPrimeFactors(div)); 
conn.recvuntil("Test number")
for x in range (100):    conn.recvuntil("gcd(x, y) = ")    g = conn.recvline()    conn.recvuntil("lcm(x, y) = ")    l = conn.recvline()
    payload = countPairs(int(g), int(l))    conn.sendline(str(int(payload)))    print(x+1, conn.recvline().decode("utf-8"))
conn.interactive()```
```shell[*] Switching to interactive modeWow, you really know this kind of weird math?Here's your flag: X-MAS{gr347es7_c0mm0n_d1v1s0r_4nd_l345t_c0mmon_mult1pl3_4r3_1n73rc0nn3ct3d}[*] Got EOF while reading in interactive```
Flag: X-MAS{gr347es7_c0mm0n_d1v1s0r_4nd_l345t_c0mmon_mult1pl3_4r3_1n73rc0nn3ct3d}