Cod sursa(job #718107)

Utilizator algotrollNume Fals algotroll Data 20 martie 2012 15:33:20
Problema Suma si numarul divizorilor Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include<cstdio>
#include<cmath>
#include<vector>
#define _CIURMAX 1000010
#define MOD 9973
typedef unsigned long long ull;

std::vector<int> lPrime;
void ciuruieste()
{
    static bool compus[_CIURMAX];
    for (int i=3;i<_CIURMAX;i+=2)
        if (!compus[i])
        {
            lPrime.push_back(i);
            if (i<=sqrt(_CIURMAX)) for (int k=i*i;k<_CIURMAX;k+=i)
                compus[k]=1;
        }
}

ull pow(int base, int exp)
{
    if (exp==1) return base;
    if (exp%2==0) return pow(base,exp/2)*pow(base,exp/2);
    else return pow(base,exp/2)*pow(base,exp/2)*base;
}

void print_nr_sum(ull);
int main()
{
    ciuruieste();
    freopen("ssnd.in","r",stdin);
    freopen("ssnd.out","w",stdout);
    int nNr; scanf("%d", &nNr);
    for (int i=1;i<=nNr;i++)
    {
        ull n; scanf("%llu",&n);
        print_nr_sum(n);
    }
    return 0;
}

void print_nr_sum(ull n)
{
    ull nDiv, sum;
    int exp=0;
    for (;n%2==0;n/=2) exp++;
    nDiv=(exp+1);
    sum=pow(2,exp+1)-1;
    for (std::vector<int>::iterator pPr=lPrime.begin(); *pPr<=n; ++pPr)
    {
        if (n%*pPr!=0) continue;
        for (exp=0;n%*pPr==0;n/=*pPr) exp++;
        nDiv*=(exp+1);
        sum=(pow(*pPr,exp+1)-1)/(*pPr-1)*sum %MOD;
    }
    printf("%llu %llu\n",nDiv,sum);
}