Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define ll long long
- using namespace std;
- ll n,k,t;
- ll solve(ll n,ll k){
- // generating the prime factors of k and storing it in vector
- vector<ll> store;
- for(ll i=2;i<=sqrt(k);i++){
- if(k%i==0){
- while(k%i==0){
- k=k/i;
- store.push_back(i);
- }
- }
- }
- if(k!=1)
- store.push_back(k);
- // store has all the prime factors of k
- ll maxx=INT_MIN;
- for(int i=0;i<store.size();i++){
- if(store[i]>maxx)
- maxx=store[i];
- }
- // find the prime exponent of this max prime number
- ll x=1,res=0;
- while((n/(pow(maxx,x)))!=0){
- res+=n/(pow(maxx,x));
- x+=1;
- }
- return res;
- }
- int main(){
- cin>>t;
- while(t--){
- cin>>n>>k;
- cout<<solve(n,k)<<endl;
- }
- }
Add Comment
Please, Sign In to add comment