Cod sursa(job #494600)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 22 octombrie 2010 11:10:50
Problema Suma si numarul divizorilor Scor 100
Compilator cpp Status done
Runda tema_1_10f Marime 0.88 kb
#include<cstdio>
#define MOD 9973
#define LL long long
bool f[1<<20];
int NRP,p[1<<19];
void ciur()
{
	for(int i=2;i<=1000000;i++)
		if(f[i]==0)
		{
			p[++NRP]=i;
			if((long long)i*i<1000000)
				for(int j=(long long)i*i;j<=1000000;j+=i)
					f[j]=true;
		}
}
void solve(long long x)
{
	int nrdiv=1,sdiv=1;
	for(int i=1;(long long)p[i]*p[i]<=x;i++)
		if(x%p[i]==0)
		{
			long long put=1;
			int nrp=0;
			while(x%p[i]==0)
				nrp++,put*=(LL)p[i], x/=p[i];
			nrdiv*=(nrp+1);
			sdiv*=(((put*(LL)p[i]-1)/((LL)p[i]-1))%MOD);
			sdiv%=MOD;
		}
	if(x>1)
	{
		nrdiv*=2;
		sdiv*=((((LL)x*x-1)/(x-1))%MOD);
		sdiv%=MOD;
	}
	printf("%d %d\n",nrdiv,sdiv);
}
int main()
{
	freopen("ssnd.in","r",stdin);
	freopen("ssnd.out","w",stdout);
	int n;
	ciur();
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		long long x;
		scanf("%lld",&x);
		solve(x);
	}
	return 0;
}