- Say X and Y are no. of pairs for x1 and y1 in range [x2,y2] where y/x = k^n
- So all the numbers b/w x1 and y1 have pairs b/w X and Y.
- So, for range i => X to Y, find interval where no. of pairs are i
But this is failing.This soln. looks promising to me, Please help me why this will not work. TIA
ll solve(ll x, ll p, ll q, ll k) { ll pow = 0, X = 0; while(true) { ll num = x * power(k,pow); if(num>=p and num<=q) X++; else if(num>q) break; pow++; } return X; } int main(){ ll t = 1; cin>>t;
while(t--) {
ll k, a,b, p,q;
cin>>k>>a>>b>>p>>q;
// find no of soln. for "a"
ll pow = 0, X = 0;
while(true) {
ll num = a * power(k,pow);
if(num>=p and num<=q) X++;
else if(num>q) break;
pow++;
}
// find no of soln. for "b"
pow = 0; ll Y = 0;
while(true) {
ll num = b * power(k,pow);
if(num>=p and num<=q) Y++;
else if(num>q) break;
pow++;
}
ll result = 0, prev = a;
for(int i=X;i>=Y;i--) {
// find how many numbers have "i" pairs
ll low = a, high = b;
ll ans = 0;
while(low <= high) {
ll mid = (low + high)/2;
// find "mid" range in a->b
ll res = solve(mid,p,q,k);
if (res>=i){
ans = mid;
low = mid+1;
}
else high = mid-1;
}
result += i * (ans - prev + 1);
// cout<<i<<": "<<prev<<" "<<ans<<E;
prev = ans+1;
}
cout<<result<<E;
}}




