Pagini recente » Cod sursa (job #35517) | Cod sursa (job #96920) | Cod sursa (job #2003881) | Cod sursa (job #2033639) | Cod sursa (job #482332)
Cod sursa(job #482332)
#include<fstream>
#include<iostream>
#include<bitset>
using namespace std;
typedef unsigned long long uint64;
const unsigned int MOD = 9973;
template<unsigned long numbits>
struct PrimeSieve
{
long long num;
bitset<numbits> bits;
void GeneratePrimes(const long long n)
{
num=1;
for(int i=1; ((i<<1)+1)*((i<<1)+1)<n; ++i)
{
if(!bits[i])
{
for(long long j=i; ((i<<1)+1)*((j<<1)+1)<n; ++j)
{
const long long index=((i<<1)+1)*((j<<1)+1);
//cout<<"("<<((i<<1)+1)*((j<<1)+1)<<" "<<(i+j)+1<<")"<<" ";
bits[index>>1]=1;
}
}
}
}
const bitset<numbits>& GetPrimes() const
{
return bits;
}
};
uint64 powl(uint64 n, int p)
{
uint64 rez=1;
while(p)
{
if(p&1)
{
rez*=n;
}
n*=n;
p>>=1;
}
return rez;
}
void Decompose(uint64& n, uint64 div, uint64& p, uint64& d)
{
d=p=0;
while(n % div == 0)
{
p=div;
d++;
n/=p;
}
}
int main()
{
int t;
uint64 n,p,d;
fstream fin("ssnd.in", fstream::in);
fstream fout("ssnd.out", fstream::out);
PrimeSieve<1000002> primes;
primes.GeneratePrimes(1000001);
fin>>t;
//cout<<t<<endl;
for(int l=0; l<t; ++l)
{
fin>>n;
//n=1600200055;
uint64 i=1,aux=n;
uint64 s=1,numdiv=1;
Decompose(n, 2, p, d);
if(p)
{
//cout<<p<<" - "<<d<<endl;
numdiv*=(d+1);
s=(s*((powl(p,d+1)-1)/(p-1)))%MOD;
}
while(n>1 && (((i<<1)+1)<<1)<=aux)
{
if(!(primes.GetPrimes())[i])
{
//cout<<"here "<<index<<endl;
const uint64 index=(i<<1)+1;
Decompose(n, index, p, d);
if(p)
{
//cout<<p<<" "<<d<<endl;
numdiv*=(d+1);
//cout<<powl(p,d)<<endl<<endl;
s=(s*((powl(p,d+1)-1)/(p-1)))%MOD;
}
}
i++;
//cout<<(i<<1)+1<<endl;
}
if(n>1)
{
s=n+1;
}
fout<<numdiv<<" "<<s<<endl;
}
fin.close();
fout.close();
return 0;
}