Codeforces Round 993 (Div. 4) Editorial
It’s not feasible to check all pairs of x and
y because it takes O(n^2) time, but it’s possible for
n. Even with the most strict case k=2, we only
need to check
n = 1, 2, 3, ..., 32 (2 ^ 32 = 4294967296 > 10 ^ 9).
Once n is fixed, we can simply count the intersection of
two conditions.
for i in range(int(input())):
k, l1, r1, l2, r2 = map(int, input().split())
kn, ans = 1, 0
while r2 // kn >= l1:
# count the integer points in the intersection of
# A. l1 <= x <= r1
# B. ceil(l2 / k^n) <= x <= floor(r2 / k^n)
# upper bound: min(r1, floor(r2 / k^n))
# lower bound: max(l1, ceil(l2 / k^n))
ans += max(
0,
min(r2 // kn, r1) - max((l2 - 1) // kn + 1, l1) + 1,
)
kn *= k
print(ans)In general, you can count the number of integer points in the
intersection A and B, which is
max(0, min(upper bounds) - max(lower bounds) + 1)It looks too obvious once I get to know the technique.
TIL
TODO: