In this HackerEarth Base numbers problem solution you are given three integers a, b, and n. Your task is to determine the number of positive integers x related to [1,10^9] such that ax^x is an n-digit number of base b.


HackerEarth Base numbers problem solution


HackerEarth Base numbers problem solution.

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <deque>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define qi ios::sync_with_stdio(0)

bool debug=true;
template<typename T1,typename T2>ostream& operator<<(ostream& os,pair<T1,T2> ptt){
os<<ptt.first<<","<<ptt.second;
return os;
}
template<typename T>ostream& operator<<(ostream& os,vector<T> vt){
os<<"{";
for(int i=0;i<vt.size();i++){
os<<vt[i]<<" ";
}
os<<"}";
return os;
}

ll a,n,b;
inline double log(ll a,ll b){
return log10(a)/log10(b);
}

inline bool ok(ll x,ll n){
long double v=floor(x*log(x,b)+log(a,b))+1;
if(v>=n){
return true;
}else{
return false;
}
}

void solve(){
ll l=0,r=1e9;
while(l<=r){
ll m=(l+r)/2;
if(ok(m,n)){
r=m-1;
}else{
l=m+1;
}
}
ll l2=0,r2=1e9;
while(l2<=r2){
ll m=(l2+r2)/2;
if(ok(m,n+1)){
r2=m-1;
}else{
l2=m+1;
}
}

cout<<l2-l<<endl;
}

int main(int argc,char* argv[]){
while(cin>>a>>n>>b){
solve();
}
return 0;
}