* 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;↵
} ↵
}hERE'S the submission: [submission:296696384]
* 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 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;↵
} ↵
}
