Pagini recente » Rezultatele filtrării | Diferente pentru problema/tije intre reviziile 6 si 3 | Diferente pentru problema/karma intre reviziile 2 si 3 | Borderou de evaluare (job #468108) | Cod sursa (job #558114)
Cod sursa(job #558114)
#include <vector>
#include <fstream>
#include <cstdlib>
#define N_MAX 62502
#define ValueMax 1000010
#define MODULO 9973
using namespace std;
char isPrime[N_MAX];
vector< int > PrimeNr;
inline bool isSet( int k ) { return 1 == ( isPrime[k>>3] & (1<<(k&7)) ); }
inline void Set( int k ) { isPrime[k>>3]|=1<<(k&7); }
inline void Sieve()
{
int i, j, _count;
for( i=1; ((i*i)<<1)+(i<<1) < ValueMax; ++i )
if( false == isSet(i) )
{
_count=i<<1;
for( j=((i*i)<<1)+(i<<1); (j<<1) < ValueMax; j+=_count )
Set(j);
}
PrimeNr.push_back(2);
for( i=1, j=3; j < ValueMax; j+=2, ++i )
if( false == isSet(i) )
PrimeNr.push_back(j);
}
inline void gcd( int a, int b, int& X, int& Y )
{
if( 0 == b )
{
X=1;
Y=0;
return;
}
int x0, y0;
gcd( b, a%b, x0, y0 );
X=y0;
Y=x0-(a/b)*y0;
}
inline int Inv( int X, int Mod )
{
int inv, p;
gcd( X, Mod, inv, p );
if( inv < 0 )
inv+=Mod;
return inv;
}
inline int pow( int x, int n )
{
int r=1;
for( ; n; n>>=1 )
{
if( n&1 )
{
r=(r*x)%MODULO;
--n;
}
x=(x*x)%MODULO;
}
return r;
}
int main( void )
{
int N, i, j, number, s;
ifstream in( "ssnd.in" );
ofstream out( "ssnd.out" );
Sieve();
in>>N;
while( in>>N )
{
number=s=1;
vector< int > divWithN;
for( i=0; 1LL*PrimeNr[i]*PrimeNr[i] <= N; ++i )
if( 0 == N%PrimeNr[i] )
{
for( j=1; 0 == N%PrimeNr[i]; N/=PrimeNr[i], ++j );
number*=j;
s=( 1LL*s*( pow( PrimeNr[i], j )-1 )*Inv( PrimeNr[i]-1, MODULO ) )%MODULO;
}
if( N > 1 )
{
number*=2;
s=( s*( N+1 ) )%MODULO;
}
out<<number<<' '<<s<<'\n';
}
return EXIT_SUCCESS;
}