Cod sursa(job #1757415)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 14 septembrie 2016 23:55:50
Problema Suma si numarul divizorilor Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int NMAX = 1000001;
int n;
long long int x;
bool mark[NMAX];
int prime[NMAX];

void ciur()
{
    for(int i=3;i*i<=NMAX;i+=2)
    {
        if(!mark[i])
            for(int j=i*i;j<=NMAX;j+=2*i)
            mark[j] = true;
    }
    int k = 1;
    prime[k] = 2;
    for(int i=3;i<=NMAX;i+=2)
        if(!mark[i])
            prime[++k] = i;
}

int main()
{
    in>>n;
    ciur();
    int nr = 0,j;
    long long int nr_d=1,sum_d = 1;
    long long int nrf;
    for(int i=1;i<=n;i++)
    {
        in>>x;
        j = 1;
        nr_d = 1;
        sum_d = 1;
        while(prime[j]*prime[j]<=x)
        {
            nr = 0;
            nrf = x;
            while(x%prime[j]==0)
            {
                nr++;
                x/=prime[j];
            }
            if(nr > 0)
            {
                nr_d*=(nr+1);
                sum_d*= (((nrf/x)*prime[j] - 1)/(prime[j]-1));
            }
            j++;
        }
        if(x!=1)
        {
            nr_d*=2;
            sum_d*= ((x*x - 1)/(x-1));
        }
        out<<nr_d<<" "<<sum_d<<"\n";
    }
    in.close();
    out.close();
    return 0;
}