fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define FR0(i,N) for(i=0;i<(N);i++)
  4. #define FR1(i,N) for(i=1;i<=(N);i++)
  5. #define FRN(i,k,N) for(i=k;i<(N);i++)
  6. #define pf printf
  7. #define db double
  8. #define max3(a,b,c) max(max(a,b),c)
  9. #define min3(a,b,c) min(min(a,b),c)
  10. #define sci(n) scanf("%d",&n)
  11. #define scl(n) scanf("%lld",&n)
  12. #define scf(n) scanf("%f",&n)
  13. #define scd(n) scanf("%lf",&n)
  14. #define scs(s) scanf("%s",&s)
  15. #define scll(n) scanf("%%I64d",&n)
  16. #define PI acos(-1.0)
  17. #define LL long long
  18. #define MX 1000005
  19. #define MOD 1000000007
  20. #define forit(i, a) for ( __typeof( a.begin() ) i = a.begin(); i != a.end(); i++ )
  21. /*
  22. 1) Find number of trailing zeroes 
  23.  
  24. Factorize the base and the factorial. Actually you don't have to factorize the factorial completely. Just calculate the prime factors present in the base. 
  25.  
  26. e.g. in base 10, 10 = 2 * 5 
  27. 100! contains: 
  28. 2^(some number that I didn't compute) * 5 ^ 24. Obviously, 5 is the limiting factor here and thus the number of trailing zeroes is 24. (Other prime factors not in base are not important). 
  29.  
  30. (2) Find number of digits in base representation 
  31.  
  32. Use log. When logged by a certain base, you will get the number of digits in the representation of the number in that base (round down). 
  33.  
  34. e.g. log (base 10) 89 = 2.???, therefore the number of digits is 2 (for 89 represented in decimal). 
  35.  
  36. Two basic identities: 
  37.  
  38. log (base x) (some_value) = ln (some_value) / ln x (ln = natural log) 
  39.  
  40. log ab = log a + log b 
  41. (naturally implies log n! = log 1 + log 2 + log 3 + log 4 + ... + log n which is one way to attack this problem) 
  42. */
  43. typedef long long int ll;
  44. bool status[1100002];
  45. vector<int>prime;
  46. void siv()
  47. {
  48.     int N=30;
  49.     for(int i=2; i<N; i++)
  50.     {
  51.         prime.push_back(i);
  52.         for(int j=2; j<i; j++)
  53.         {
  54.             if(i%j==0)
  55.             {
  56.                 prime.pop_back();
  57.                 break;
  58.             }
  59.         }
  60.     }
  61. }
  62. void prime_factorization(int n,map<int,int>&f)
  63. {
  64.     for(int i=0;i<prime.size();i++)
  65.     {
  66.         if(n==1) break;
  67.         while(n%prime[i]==0)
  68.         {
  69.             f[prime[i]]++;
  70.             n/=prime[i];
  71.         }
  72.     }
  73.     if(n!=1) f[n]++;
  74. }
  75. int count(int n,int f)
  76. {
  77.     int ret=0;
  78.     while(n)
  79.     {
  80.         ret+=n/f;
  81.         n/=f;
  82.     }
  83.     return ret;
  84. }
  85. int main()
  86. {
  87.  siv();
  88.  int n,b;
  89.  while(cin>>n>>b)
  90.  {
  91.      map<int,int>f;
  92.      prime_factorization(b,f);
  93.      int zero=INT_MAX;
  94.      forit(it,f)
  95.      {
  96.         zero=min(zero,count(n,it->first)/it->second);
  97.      }
  98.      double digit=0.0;
  99.      for(int i=1;i<=n;i++)
  100.      {
  101.          digit+=log(i)/log(b);
  102.      }
  103.      pf("%d %d\n",zero,(int)floor(digit+1e-9)+1);
  104.  }
  105. }
  106.  
Success #stdin #stdout 0s 4536KB
comments (?)
stdin
copy 
2 10
5 16
5 10
stdout
copy 
0 1
0 2
1 3
https://ideone.com/O8SYSD
language:
C++14 (clang 8.0)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!