Cod sursa(job #491390)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 11 octombrie 2010 09:10:01
Problema Suma si numarul divizorilor Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include<stdio.h>
#include<string.h>
#define Ld 1000000
#define MOD 9973
#define divizori 80000
using namespace std;
int T,i,prim[divizori],ciur[Ld+10],P,e,d;
int Sum;
long long Nrdiv;
long long n;

void precalc()
{
	int i,j;
	
	for(i=2;i<=Ld;++i)
		if(!ciur[i])
		{
			prim[++P]=i;
			if ((long long)i * (long long)i > (long long)Ld) continue;
			for(j=i*i;j<=Ld;j+=(i<<1))
				ciur[j]=1;
		}
}

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

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