fork download
copy 
  1. /**
  2.  *   author: malviyanshiv
  3.  *   created: 10 February 2019  20:15:50
  4. **/
  5.  
  6. #include <bits/stdc++.h>
  7.  
  8. using namespace std;
  9.  
  10. #define REP(i, a, b) for(int i = a; i < b; i++)
  11. #define RREP(i, a, b) for(int i = a-1; i >= b; i--)
  12.  
  13. #define FORE(a) for(auto ele : a )
  14. #define PB push_back
  15. #define MP make_pair
  16. #define MOD 1000000007
  17. #define INF 0x7fffffff
  18. #define LINF 2000000000000000007
  19. #define F first
  20. #define S second
  21. #define TC int t; cin >> t; while(t--)
  22. #define ALL(a) begin(a), end(a)
  23. #define MAX 1000005
  24.  
  25. typedef long long ll;
  26. typedef pair< int, int > PII;
  27.  
  28.  
  29. void optimizeIO(){
  30.     ios_base::sync_with_stdio(false); 
  31.     cin.tie(NULL);
  32. }
  33.  
  34. int main(){
  35.     optimizeIO();
  36.  
  37.     ll n,b;
  38.     cin >> n >> b;
  39.     vector<bool> prime(MAX, 1);
  40.     bool is_prime = true;
  41.     for(ll i = 2; i < MAX; i++){
  42.         if( prime[i] == 1 ){
  43.             if( is_prime && b%i == 0 && i != b)
  44.                 is_prime = false;
  45.             for(ll j = 2*i; j < MAX; j+=i)
  46.                 prime[j] = 0;
  47.         }
  48.     }
  49.     if( is_prime ){
  50.         ll pw = 0;
  51.         ll j = b;
  52.         ll temp=1;
  53.         ll mmm = log2(n)/log2(b);
  54.         while( temp <= mmm ){
  55.             pw += (n/j);
  56.             j = j*b;
  57.             temp++;
  58.         }
  59.         cout << (pw) << endl;
  60.         return 0;
  61.     }
  62.     ll res = LINF;
  63.  
  64.     for(ll i = 2; i < MAX; i++){
  65.         if( prime[i] && b%i == 0 ){
  66.             ll pw = 0;
  67.             ll j = i;
  68.             ll temp = 1;
  69.             ll mmm = log2(n)/log2(i);
  70.             while( temp <= mmm ){
  71.                 pw += (n/j);
  72.                 j = j*i;
  73.                 temp++;
  74.             }
  75.             ll tb = b;
  76.             ll cnt = 0;
  77.             while( tb%i == 0 )
  78.                 tb = tb/i, cnt++;
  79.             res = min( res, (ll)(pw/cnt));
  80.         }
  81.     }
  82.     cout << res << endl;
  83.  
  84.     return 0;
  85. }
Success #stdin #stdout 0s 15360KB
comments (?)
stdin
copy 
5 10
stdout
copy 
1
https://ideone.com/oFOZRQ
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

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!