Cod sursa(job #598887)

Utilizator dspMihaiDespotovici Mihai dspMihai Data 27 iunie 2011 14:28:06
Problema Suma si numarul divizorilor Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>
#include <bitset>
#define Nmare 1000005
#define MOD 9973
using namespace std;
int t,K,P[Nmare];
long p,crt,i,j,nr[1001];
bitset <Nmare> ciur;

void creare_ciur (void)
{
	for (i=2; i<=Nmare; i++)
		if (!ciur[i])
		{
			P[++K]=i;
			for (j=i+i; j<=Nmare; j+=i) ciur[j]=1;
		}
}

int pow (int x,int y)
{
	int rez=1;
	for(;y>0;y--) rez=(rez*x)%MOD;
	return rez;
}
void rezolvare (void)
{
	scanf("%d", &crt);
	long nr=1,S=1,N=crt;
	if (crt==1) printf("1 1\n");
	else if (ciur[crt])
	{
		for (i=1; i<=K && P[i]<=N/2; i++)
		{
			p=0;
			while (crt%P[i]==0) {p++; crt/=P[i];}
			if (p)
			{
				nr=(p+1)*nr;
				S=(S*(pow(P[i],p+1)-1)/(P[i]-1))%MOD;
			}
		}
		printf("%d %d\n", nr,S);
	}
	else 
	{
		printf("2 %d\n", crt+1);
	}
}

int main ()
{
	creare_ciur();
	
	freopen("ssnd.in", "r",stdin);
	freopen("ssnd.out", "w",stdout);
	scanf("%d", &t);
	for (; t>0; t--) rezolvare();
	return 0;
}