Pagini recente » Cod sursa (job #2496201) | Cod sursa (job #126866) | Cod sursa (job #987828) | Cod sursa (job #2362900) | Cod sursa (job #494600)
Cod sursa(job #494600)
#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;
}