Cod sursa(job #650818)

Utilizator bhaskruMarius S bhaskru Data 18 decembrie 2011 23:37:00
Problema Suma si numarul divizorilor Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.1 kb
#include <stdio.h>
FILE *f,*g;
int v[1000001];
int prim[100000];

void ciur()
{
    int j,i;
    prim[0]=1;
    prim[1]=2;
    for(i=3; i<=1000000; i+=2)
    {
        if(v[i]==0)
        {
            prim[++prim[0]]=i;
            for(j=3*i; j<=1000000; j+=2*i)
                v[j]=1;
        }
    }
}

void desco(long long x)
{
    long nr, sum, t, i, exp;
    nr=sum=1;
    for(i=1; prim[i]*prim[i]<=x ; i++)
    {
        if(x%prim[i]==0)
        {
            exp=1;
            t=prim[i];
            while(x%prim[i]==0)
            {
                exp++;
                x=x/prim[i];
                t=t*prim[i];
            }
            nr*=exp;
            sum*=(t-1)/(prim[i]-1)%9973;
        }
    }
    if(x!=1)
    {
        sum*=(x*x-1)/(x-1)%9973;
        nr*=2;
    }
    printf("%ld %ld\n",nr,sum%9973);
}

int main()
{
    long n, q;
freopen("ssnd.in", "r", stdin);
freopen("ssnd.out", "w", stdout);
    ciur();
    fscanf(f,"%ld",&n);
    while(n!=0)
    {
        scanf("%ld",&q);
        desco(q);
        n=n-1;
    }
    return 0;
}