Guest User

Untitled

a guest
Jan 11th, 2020
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.70 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. ll n,k,t;
  5. ll solve(ll n,ll k){
  6.     // generating the prime factors of k and storing it in vector
  7.     vector<ll> store;
  8.     for(ll i=2;i<=sqrt(k);i++){
  9.         if(k%i==0){
  10.             while(k%i==0){
  11.                 k=k/i;
  12.                 store.push_back(i);
  13.             }
  14.         }
  15.     }
  16.     if(k!=1)
  17.         store.push_back(k);
  18.     // store has all the prime factors of k
  19.     ll maxx=INT_MIN;
  20.     for(int i=0;i<store.size();i++){
  21.         if(store[i]>maxx)
  22.             maxx=store[i];
  23.     }
  24.     // find the prime exponent of this max prime number
  25.     ll x=1,res=0;
  26.     while((n/(pow(maxx,x)))!=0){
  27.         res+=n/(pow(maxx,x));
  28.         x+=1;
  29.     }
  30.     return res;
  31. }
  32. int main(){
  33.     cin>>t;
  34.     while(t--){
  35.         cin>>n>>k;
  36.         cout<<solve(n,k)<<endl;
  37.     }
  38. }
Add Comment
Please, Sign In to add comment