# Cod sursa(job #2495251)

Utilizator Data 18 noiembrie 2019 23:31:46 Suma si numarul divizorilor 40 cpp-64 done Arhiva educationala 1.49 kb
``````#include <bits/stdc++.h>
#define dim 1000004
#define mod 9973
using namespace std;
ifstream fin("ssnd.in");
ofstream fout("ssnd.out");
bitset <dim> fr;
long long prim[dim/10];
long long k,q,i,n,st,nr,sum,p,a;
long long x;
void  ciur()
{
fr[1]=fr[0]=1;
prim[++k]=2;
for(int i=3; i<=dim; i+=2)
{
if(fr[i]==0)
{
prim[++k]=i;
for(int j=3*i; j<=dim; j+=2*i)
fr[j]=1;
}
}
}
long long put (long long a,long long b)
{
if(b==0)
return 1;
else
if(b==1)
return a%mod;
if(b%2==0)
x=put(a*a%mod,b/2);
else
x=a*put(a*a%mod,(b-1)/2)%mod;
return x;

}
int main()
{
ciur();
fin>>q;
for(; q; q--)
{
fin>>a;
st=1;

long long nrfact=1,psus=1,pjos=1;
while(prim[st]*prim[st]<=a&&st<=k)
{
nr=0;
if(a%prim[st]==0)
{
while(a%prim[st]==0){
a/=prim[st];
nr++;
}
nrfact*=(nr+1)%mod;
psus*=(put(prim[st],nr+1)%mod+mod-1)%mod;
pjos*=(prim[st]%mod+mod-1)%mod;
}
st++;
}
if(a>1)
{
nrfact*=2;
psus*=(put(a,2)%mod+mod-1)%mod;
pjos*=(a+mod-1)%mod;
}
fout<<nrfact%mod<<" "<<(1LL*psus*put(pjos,mod-2))%mod<<"\n";
}
}
``````