Cod sursa(job #519083)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 3 ianuarie 2011 22:50:58
Problema Suma si numarul divizorilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include<stdio.h>
#include<math.h>
#define N 1000000
int test,u;
unsigned long long n,i,j,t,p[N]={0},s,nr,k,x[N];

long put(unsigned long long x,unsigned long long n)
{if(n==0)
      return 1;
if(n%2==0)
      return put(x,n/2)*put(x,n/2);
else
      return x*put(x,(n-1)/2)*put(x,(n-1)/2);}

void sieve(unsigned long long x[N],unsigned long long *k,unsigned long long p[N])
{unsigned long long i;
for(i=2;i<=N;i++)
if(p[i]==0)
      {x[++(*k)]=i;
      for(j=i+i;j<=N;j+=i)
            p[j]=1;}}

int main()
{freopen("ssnd.in","r",stdin);
freopen("ssnd.out","w",stdout);
scanf("%d\n",&test);
k=0;
sieve(x,&k,p);
for(u=1;u<=test;u++)
     {scanf("%llu\n",&n);
     j=0;
     t=n;
     i=1;
     s=1;
     nr=1;
     while(t!=1&&i<=k&&x[i]<=sqrt(n)&&x[i]<=t)
           {while(t%x[i]==0)
                  {j++;
                  t/=x[i];
                  if(t==1)
                         {nr=nr*(j+1);
                         if(j==1)
                               s=s*(x[i]+1);
                         else
                               s=s*(put(x[i],j+1)-1)/(x[i]-1);
                         j=0;}}
           if(j!=0)
                  {nr=nr*(j+1);
                  if(j==1)
                         s=s*(x[i]+1);
                  else
                         s=s*(put(x[i],j+1)-1)/(x[i]-1);
                  j=0;}
           i++;}
     if(t!=1)
           {nr=nr*2;
           s=s*(t+1);}
     if(s==1)
           {nr=2;
           s+=n;}
     printf("%llu %llu\n",nr,s);}
fclose(stdin);
fclose(stdout);
return 0;}