Cod sursa(job #523278)
#include<fstream.h>
#include<iostream.h>
#define N 1000000
int test,u,nr,v[N];
long long n,t,s;
long x[N],k,i,j,l,q,r;
void sieve(long x[N],long *k,int p[N])
{long i,l,j;
for(l=2;l<=N;l++)
p[l]=0;
for(i=2;i<=N;i++)
if(p[i]==0)
{x[++(*k)]=i;
j=i+i;
while(j<=N)
{p[j]=1;
j=j+i;}}}
int main()
{ifstream f1("ssnd.in");
ofstream f2("ssnd.out");
f1>>test;
k=0;
sieve(x,&k,v);
for(u=1;u<=test;u++)
{f1>>n;
i=1;
t=n;
s=1;
nr=1;
while(t!=1&&i<=k)
{j=0;
while(t%x[i]==0)
{j++;
t/=x[i];
if(t==1)
{nr=nr*(j+1);
q=x[i]+1;
for(r=1;r<j;r++)
q=q*x[i]+1;
s*=q;}}
if(j!=0&&t>1)
{nr=nr*(j+1);
q=x[i]+1;
for(r=1;r<j;r++)
q=q*x[i]+1;
s*=q;}
i++;}
if(t>1)
{nr*=2;
s=s*(t+1);}
if(s==1)
{nr=2;
s+=n;}
f2<<nr<<" "<<s%9973<<endl;}
f1.close();
f2.close();
return 0;}