Cod sursa(job #2442317)

Utilizator MihaIonescuMihai Ionescu MihaIonescu Data 23 iulie 2019 17:13:01
Problema Suma si numarul divizorilor Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <fstream>
#include <cmath>
using namespace std;

ifstream f ("ssnd.in");
ofstream g ("ssnd.out");

bool b[1000001];
long long num[1001];

void Ciur (int n)
{
    b[0]=b[1] = 1;

    for (int i = 4; i<=n; i+=2)
        b[i] = 1;
    for (int i = 3; i*i<=n; i+=2)
        if (b[i]==0)
            for (int j = i*i; j <= n; j+=i)
                b[j] = 1;
}

int Putere (int x, int n)
{
    if (n==0)
        return 1;
    int p = Putere(x, n/2);

    if (n%2==0)
        return p * p;
    return p * p * x;
}

void SsND (long long x, long long &sumDiv, long long &nrDiv)
{
    long long x_copy = x;
    int p = 0;
    long long presum;

    while (x%2==0)
    {
        x/=2;
        p++;
    }

    sumDiv = Putere (2, p+1) - 1;
    nrDiv = p+1;

    for (int i = 3; i*i<=x; i+=2)
        if (b[i]==0 && x%i == 0)
        {
            p = 0;
            while (x%i==0)
                x/=i, p++;
            presum = Putere(i, p+1) - 1;
            presum /= (i-1);
            sumDiv *= presum;
            nrDiv *= (p+1);
        }

    if (x>1)
    {
        nrDiv*=2;
        sumDiv *= (x+1);
    }
    if (x==x_copy)
    {
        sumDiv = x+1;
        nrDiv = 2;
    }
}

int main ()
{
    int t, num_max = -1;
    f>>t;
    for (int i = 0; i<t; i++)
    {
        f.get();
        f>>num[i];

        if (num[i] > num_max)
            num_max = num[i];
    }

   // Ciur((int)sqrt(num_max) + 1);
    Ciur(1000000);
    long long sumDiv, nrDiv;
    for (int i = 0; i<t; i++)
    {
        SsND (num[i], sumDiv, nrDiv);
        g<<nrDiv<<' '<<sumDiv<<'\n';
    }

    return 0;
}