Cod sursa(job #2302511)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 14 decembrie 2018 19:13:15
Problema Suma si numarul divizorilor Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#define NMAX 1000000
using namespace std;

ifstream fin("ssnd.in");
ofstream fout("ssnd.out");

int t;
long long x, numere_prime[1000001], z;
bool IsPrim[1000001];

void ciur()
{
    for (int i = 4; i <= NMAX; i += 2)
        IsPrim[i] = true;
    IsPrim[0] = true;
    IsPrim[1] = true;
    for (int i = 3; i * i <= NMAX; i += 2)
        for (int j = i * i; j <= NMAX; j += 2 * i)
            IsPrim[j] = true;
    numere_prime[++z] = 2;
    for (int i = 3; i <= NMAX; i += 2)
        if (!IsPrim[i])
            numere_prime[++z] = i;
}


int main()
{
    ciur();
    fin >> t;
    for (int i = 0; i < t; ++i)
    {
        fin >> x;
        long long nrdiv = 1, sumdiv =  1, c;
        for (int i = 1; i <= z && numere_prime[i] * numere_prime[i] <= x; ++i)
        {
            long long p = 0, numar = 1;
            while (x % numere_prime[i] == 0)
            {
                ++p;
                x = x / numere_prime[i];
                numar *= numere_prime[i];
            }
            if (p)
            {
                numar = ((numar * numere_prime[i]) - 1) / (numere_prime[i] - 1);
                nrdiv *= (p + 1);
                sumdiv *= numar;
            }
        }
        if (x > 1)
        {
            nrdiv *= 2;
            sumdiv *= ((x * x) - 1) / (x - 1);
        }
        fout << nrdiv << " " << sumdiv << "\n";
    }
    return 0;
}