ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1117. Hierarchy

I solved it without dp.
Posted by coolboy19521 5 Jul 2024 02:05
The solution is actually really easy when not dp. It is just the count of numbers that are divisible by (1ll<<i) and only by (1ll<<i) times 2(i-1). If you just draw 1-15 tree and try to solve for 1 15 you'll observe it. You just have to make these checks (i'm too lazy to explain it, but if you want just comment):

for (int i = 30; i >= 1; i--) {
int powerOf2 = 1ll << i;
int ci = countMultiples(n, m, powerOf2);
ci -= al;
int r = m / powerOf2;
int l = n / powerOf2;
an += 2 * (i - 1) * ci;

if (m % powerOf2 == 0 && (r % 2 != 0 || r == 0) && ci > 0) {// <-- These are the checks
an -= (i - 1);
}
if (n % powerOf2 == 0 && (l % 2 != 0 || l == 0) && ci > 0) {
an -= (i - 1);
}
al += ci;
}