Question

#664 NrPerechi

Cerința
Gigel a învăţat la matematică despre cel mai mic multiplu comun a două numere şi acum trebuie să determine pentru fiecare valoare x dintr-un set de valori date câte perechi ordonate de numere naturale (a,b) au cel mai mic multiplu comun x.

Date de intrare
Programul citește de la tastatură număr n, apoi n valori x.

Date de ieșire
Programul va afișa pe ecran n valori, separate prin exact un spaţiu; fiecare valoare afișată reprezintă numărul de perechi care au cel mai mic multiplu comun egal cu valoarea x corespunzătoare.

Restricții și precizări
1 ≤ n ≤ 1.000
1 ≤ x ≤ 2.000.000.000



Exemplu
Intrare

2
12 4
Ieșire

15 5
Explicație
Cele 15 perechi pentru care cel mai mic multiplu comun este 12 sunt: (1,12), (2,12), (3,4), (3,12), (4,3), (4,6), (4,12), (6,4), (6,12), (12,1), (12,2), (12,3), (12,4), (12,6), (12,12).

Answer 1

#include <iostream>

using namespace std;

unsigned int nr_perechi(unsigned int n)

{

   unsigned int exp, i, np=1, a=n;

   for (i=2; i*i<=a; ++i)

   {

       exp=0;

      while (a%i==0)

      {

          ++exp;  a/=i;

      }

      if (exp!=0) np=np*(2*exp+1);

   }

   if (a!=1) np*=3;

   return np;

}

int main()

{

   unsigned int n, x, i;

   cin >> n;

   for (i=1; i<=n; ++i)

   {

       cin >> x;

       cout << nr_perechi(x) << " " ;

   }

   return 0;

}