Cod sursa(job #522664)
#include <fstream>
#define LL unsigned long long
#define M 9973
using namespace std;
ifstream fin("ssnd.in");
ofstream fout("ssnd.out");
LL i,j,t,id,nrpr;
LL N,pr2[250000],S,Div;
bool pr[500010];
void ciur()
{
pr2[0]=2; nrpr=0;
for(i=1;i<=500000;i++)
{
if(!pr[i])
{
for(j=2*i*i+2*i;j<=500000;j+=2*i+1)
pr[j]=true;
pr2[++nrpr]=2*i+1;
}
}
}
inline LL pow(LL c, LL p)
{
LL R=1;
while(p>0)
{
if(p&1) R*=c;
c*=c;
p>>=1;
}
return R;
}
void factori()
{
LL c,p,A=N;
S=Div=1;
for(i=0;pr2[i]*pr2[i]<=A && N>1;i++)
{
if(N%pr2[i]==0)
{
c=pr2[i]; p=0;
while(N%pr2[i]==0)
{
N/=pr2[i];
p++;
}
LL p1=(pow(c,p+1)-1);
LL p2= (c-1);
S*=(p1/ p2);
S%=M;
Div*=(p+1);
}
}
if(N>1)
{
Div<<=1;
S*=((1LL*(N+1)) % M);
S%=M;
}
}
int main()
{
fin >> t;
ciur();
for(id=1;id<=t;id++)
{
fin >> N;
factori();
fout << Div << " ";
fout << S << '\n';
}
}