I have used binary search algorithm to find the Kth root. I have used my own recursive power function. The problem I am facing is that while computing power of numbers which are quite large they overflow long long int. I am not able to predict when not to call the power function to avoid overflow and just check nect value in binary search algo.
#include<bits/stdc++.h>
typedef long long int lli;
using namespace std;
lli power(lli a,lli b)
{
if(b==1)
return a;
if(b&1)
return apower(a,b-1);
else
return power(aa,b/2);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
lli t,n,k;
long double temp;
cin>>t;
while(t–)
{
cin>>n>>k;
if(n==0 || n==1)
{
cout<<n<<’\n’;
continue;
}
lli low=0,high=n;
lli ans=0;
while(low<=high)
{
lli mid=(low+high)/2;
temp=power(mid,k);
cout<<"temp: “<<temp<<” mid: "<<mid<<’\n’;
if(temp==n)
{
ans=mid;
break;
}
if(temp<n)
{
ans=mid;
low=mid+1;
}
else
{
high=mid-1;
}
}
cout<<ans<<’\n’;
}
return 0;
}