Cod sursa(job #1553073)

Utilizator KarewitToader Petru Catalin Karewit Data 19 decembrie 2015 10:47:58
Problema Suma si numarul divizorilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>

using namespace std;
ifstream fin("ssnd.in");
ofstream fout("ssnd.out");
int ciur[1000005];
int prim[1000000];
int main()
{
    int t,nd=1,s=0, p;
    long long n=1000000;
    prim[1]=2;
    int np=1;
    for(int d=2; d*d<=n; d++)
        for(int i=d*d; i<=n; i=i+d)
            ciur[i]=1;
    for(int d=2; d*d<=n; d++)
        if(ciur[d]==0)
        {
            prim[++np]=d;
            for(int i=d*d; i<=n; i=i+2*d)
                ciur[i]=1;
        }
    fin>>t;
    for(int i=0; i<t; i++)
    {
        nd=1;
        s=1;
        fin>>n;
        for(int d=1; prim[d]*prim[d]<=n; d++)
        {
            int exp=1;
            p=prim[d];
            while(n%prim[d]==0)
            {
                exp++;
                p*=prim[d];
                n=n/prim[d];
            }
            nd*=exp;
            s*=(p-1)/(prim[d]-1);
        }
        if(n!=1)
        {
            nd*=2;
            s=s*(n*n-1)/(n-1);
        }
        fout<<nd<<' '<<s<<'\n';
    }
}