• 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;
}

}