Cod sursa(job #492400)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 14 octombrie 2010 13:41:46
Problema Suma si numarul divizorilor Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<stdio.h>
#define Ld 1000000
#define Mod 9973

int i,j,d,fact[80010],ciur[Ld+10],ex,P,T,f1,f2,NrDiv,Sum;
long long n;

void precalc()
{
	int i,j;
	
	fact[++P] = 2;
	for( i = 3 ; i <= Ld ; i+=2 )
		if( !ciur[i] ) 
		{
			fact[++P] = i;
			if( 1LL * i * i <= 1LL * Ld )
			for( j = i*i ; j <= Ld ; j+=(i<<1) )
				ciur[j] = 1 ;
		}
}	

int lgput(int a, int b)
{
	int s;
	
	for( s = 1 ; b ; a = (a*a) % Mod, b>>=1 )
		if ( b&1 )
			s = ( s * a ) % Mod;
	
	return s;	
}

int main()
{
	freopen("ssnd.in","r",stdin);
	freopen("ssnd.out","w",stdout);
	
	scanf("%d",&T);
	
	precalc();
	
	for( ; T ; --T )
	{
		scanf("%lld",&n);
		
		NrDiv = 1 ;
		Sum = 1 ;
		
		for( d = 1 ; 1LL * fact[d] * fact[d] <= n ; ++d )
		{
			if( n % fact[d] == 0 )
			{
				ex = 1 ;
				
				while( n % fact[d] == 0 )
				{
					ex++; 
					n /= fact[d];
				}
				
				NrDiv *= ex ;
				
				f1 = lgput( fact[d],ex ) - 1 ;
				f2 = lgput( fact[d]-1, Mod-2 ); 
				
				Sum *= f1 ; Sum %= Mod;
				Sum *= f2 ; Sum %= Mod;
			}
		}
		
		if( n > 1 )
		{
			NrDiv<<=1;
			Sum *= (n+1) ; 
			Sum %= Mod   ;
		}
		
		printf("%d %d\n",NrDiv,Sum);
	}
	
	return 0;
}