Cod sursa(job #496191)

Utilizator nightwish0031Vlad Radu Cristian nightwish0031 Data 28 octombrie 2010 09:00:03
Problema Suma si numarul divizorilor Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<cstdio>

int prim[50000];
const int N=1<<20;
const int MOD=9973;
bool c[N];

void ciur()
{
	int i,j;
	for (i=2;i*i<N;++i)
		if (c[i]==false)
			for (j=i*i;j<N;j+=i)
				c[j]=true;
			
	for (i=2;i<N;++i)
		if (c[i]==false)
			prim[++prim[0]]=i;
}

void fisiere()
{
	freopen("ssnd.in","r",stdin);
	freopen("ssnd.out","w",stdout);
}

int putere(int x,int p)
{
	int pp=1;
	
	while (x&&p)
	{
		pp=pp*x%MOD;
		--p;
	}
	return pp;
}

void prelucreaza(long long n)
{
	
	int e,nd=1,p;
	long long sd=1;
	int nn=1;
	while(prim[nn]<=n&&n>1&&nn<=prim[0])
	{
		e=0;
		while ((long long)n%(long long)prim[nn]==0)
		{
			++e;
			n=(long long)n/(long long)prim[nn];
		}
		if (e)
		{
			nd=nd*(e+1);
			p=putere(prim[nn],e+1);
			sd=(long long)sd*(long long)(p-1)/(long long)(prim[nn]-1)%(long long)MOD;
		}
		++nn;
	}
	
	if (n!=1)
	{
		nd=nd*2;
		p=putere(n,2);
		sd=sd*(n+1)%(long long)MOD;
	}
	printf ("%d %d\n",nd,(int)sd);
}

void citeste()
{
	int i,t;
	long long n;
	
	fisiere();
	scanf("%d",&t);
	for (i=1;i<=t;++i)
	{
		scanf("%lld",&n);
		prelucreaza(n);
	}
}

int main()
{
	ciur();
	citeste();
	
	return 0;
}