Code: Select all
joachim@joabox[p10061.cpl]$ a.out <test.txt
29262 398004
801 5973
19 75
4289 50675
754 102203
3204 35113
9 33
43 5631
joachim@joabox[p10061.cpl]$
Moderator: Board moderators
Code: Select all
joachim@joabox[p10061.cpl]$ a.out <test.txt
29262 398004
801 5973
19 75
4289 50675
754 102203
3204 35113
9 33
43 5631
joachim@joabox[p10061.cpl]$
Code: Select all
#include <iostream>
#include <cmath>
using namespace std;
#define N 800
#define ISPRIME(n) (!(prime[(n)>>4]&(1<<(((n)&15)>>1))))
#define MASK(n) (1<<(((n)&15)>>1))
unsigned char prime[N>>4];
//sieve prime from 1 to N
void sievePrimes()
{
long i,j,k,l;
for(i=0;i<=N>>4;i++)
prime[i]=0;
prime[0]++;
k=long(sqrt(double(N)));
for(i=3;i<=k;i+=2)
{
if(ISPRIME(i))
{
l=i<<1;
for(j=i*i;j<=N;j+=l)
prime[j>>4]|=MASK(j);
}
}
}
//get the totol number of the prime
long getTotolPrime()
{
long i;
long totol=1;
for(i=3;i<N;i+=2)
{
if(ISPRIME(i))
{
//cout<<i<<endl;
totol++;
}
}
return totol;
}
void main()
{
//n!=sqrt(2*pi*n)*[(n/e)^n];
long primeTab[139];
sievePrimes();
long i,j;
primeTab[0]=2;
for(i=3,j=1;i<=800;i+=2)
{
if(ISPRIME(i))
primeTab[j++]=i;
}
long min;
double pi=2*acos(double(0.0));
double e=exp(double(1.0));
long a,b;
long len;
while(cin>>a)
{
cin>>b;
len=floor((log(2*pi*a)/2+a*log(a/e))/log(double(b))+0.000001)+1;
long tb=b;
long ta;
long times,count,tmp;
min=999999999;
for(i=0;i<139;i++)
{
times=0;
count=0;
ta=a;
while(tb%primeTab[i]==0)
{
times++;
tb=tb/primeTab[i];
}
if(times>0)
{
while(ta>0)
{
ta=ta/primeTab[i];
count+=ta;
}
tmp=count/times;
if(tmp<min)
min=tmp;
}
if(tb<=1)
break;
}
cout<<min<<' '<<len<<endl;
}
}
Code: Select all
2 9
100 23
23 101
23233 344
34 799
Code: Select all
0 1
4 117
0 12
552 36014
0 14
Code: Select all
Cut after AC :)
Code: Select all
long veces(long n, long factor)(notice the changes in declaration, all is long now :))
{
//int s=0;
long s = 0;
//while( n>=factor )
while (n) // I made a change here
{
n/=factor;
s+=n;
}
return s;
}
Code: Select all
// int ceros(int n, int b)
long ceros (long n, long b)
{
/*int*/long cantidad[139]={0},factor[139];
/*int*/long t,i,j,min;
for(j=0,i=0;b!=1;++i)
{
if( b%p[i]==0)
{
factor[j]=p[i];
while(b%p[i]==0 && b>1)
{
++cantidad[j];
b/=p[i];
}
++j;
}
}
for(i=0,min=10000000l;i<j;++i) // some change in min value
{
t=veces(n,factor[i])/cantidad[i];
if(t<min)
{
min=t;
}
}
return min;
}
/*
I guess the value assigned in min may be bigger than the value that can be hold by an int, so, i made it long and i used the prefix "L" to denote it as long
*/
Code: Select all
for(sum=0.0,i=1;i<=n;++i) // change in indexing
sum+=(log10(i)/log10(b)); // change
// cout<<ceros(n,b)<<" "<<int(floor(sum/log10(b)))+1<<"\n";
cout<<ceros(n, b)<<" ";
if (sum - floor(sum) < 1e-14)
sum ++;
else
sum = floor(sum + 1);
printf("%.0lf\n", sum);
}
Code: Select all
#include<iostream>
#include<cmath>
#include<vector>
int maxp(double n,double b) //to get max power of b in n for factorization
{
int a=0;
double s=b;
while(int(n/s)!=0)
{
a+=int(n/s);
s*=b;
}
return a;
}
using namespace std;
int main()
{
if(n==0)
{cout<<"0 0"<<endl;continue;}
double n,b;
vector<long> pr;//list of primes below 300
pr.push_back(2);
pr.push_back(3);
pr.push_back(5);
pr.push_back(7);
pr.push_back(11);
pr.push_back(13);
pr.push_back(17);
pr.push_back(19);
pr.push_back(23);
pr.push_back(29);
pr.push_back(31);
pr.push_back(37);
pr.push_back(41);
pr.push_back(43);
pr.push_back(47);
pr.push_back(53);
pr.push_back(59);
pr.push_back(61);
pr.push_back(67);
pr.push_back(71);
pr.push_back(73);
pr.push_back(79);
pr.push_back(83);
pr.push_back(89);
pr.push_back(97);
pr.push_back(101);
pr.push_back(103);
pr.push_back(107);
pr.push_back(109);
pr.push_back(113);
pr.push_back(127);
pr.push_back(131);
pr.push_back(137);
pr.push_back(139);
pr.push_back(149);
pr.push_back(151);
pr.push_back(157);
pr.push_back(163);
pr.push_back(167);
pr.push_back(173);
pr.push_back(179);
pr.push_back(181);
pr.push_back(191);
pr.push_back(193);
pr.push_back(197);
pr.push_back(199);
pr.push_back(211);
pr.push_back(223);
pr.push_back(227);
pr.push_back(229);
pr.push_back(233);
pr.push_back(239);
pr.push_back(241);
pr.push_back(251);
pr.push_back(257);
pr.push_back(263);
pr.push_back(269);
pr.push_back(271);
pr.push_back(277);
pr.push_back(281);
pr.push_back(283);
pr.push_back(293);
while(cin>>n>>b)
{
double factl=0,base=b;
for(long t1=1;t1<=n;t1++)
factl+=log10(t1);
vector<long> bfact;
vector<long> nfact;
vector<long>::iterator r;
vector<long>::iterator t;
for(r=pr.begin();r!=pr.end();r++) //factorizing the base
{
long f=0;
while(b==long(b/(*r))*(*r))
{
f++;
b=b/(*r);
}
bfact.push_back(f);
}
r=pr.begin();
while((*r)<=n&&r!=pr.end())//factorizing the number
{
nfact.push_back(maxp(n,(*r)));
r++;
}
while(nfact.end()-nfact.begin()!=bfact.end()-bfact.begin()) //making the array lengths equal
nfact.push_back(0);
t=nfact.begin();
r=bfact.begin();
long min=*t; //taking one of the values as starting minimum value
long tmp=min;
while(r!=bfact.end()&&t!=nfact.end()) //checking how many times the base perfectly divides number
{
long div;
if((*r)==0&&(*t)==0)
{div=tmp;}
else if((*r)==0&&(*t)!=0)
{div=tmp;}
else if((*t)==0&&(*r)!=0)
div=0;
else
div=(*t)/(*r); //finding minimum times a prime factor of base can divide number
t++;r++;
if(div<min)
min=div;
}
cout<<min<<" "<<long(factl/log10(base))+1<<endl;
}
}