Street Checkers
Time limit40sMemory limit1024 MB
Count numbers X in [L, R] where the counts of odd and even divisors of X differ by at most 2, with R-L up to 100000 and up to 100 test cases.
- Level
Medium6 of 10
- Topics
- Number theory, Math, Implementation, Brute force
- Solved
- No attempts yet
Problem
Alice and Bob are playing a new virtual reality team game, Street Checkers. The game is set on a very long street divided into tiles numbered from 0 to 10^9 (inclusive of both). At the start of the game, Alice and Bob stand on tile 0 and are given a random number X in the range [L, R] (both ends inclusive). Alice only jumps to odd numbered tiles, while Bob only jumps to even numbered tiles. If the number on a tile divides X, the player landing on it must color it with their favorite color. The game is over after tile X has been colored.
Both players consider a game interesting if the absolute difference between the number of tiles each has painted is not greater than 2. Help Alice and Bob find how many numbers in the interval [L, R] make for an interesting game.
Input
The first line of the input gives the number of test cases, T. Each of the following T lines contains two integers L and R, the start and end of the interval used to generate the random number X.
Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the count of numbers in the interval [L, R] that make for an interesting game for Alice and Bob.
Constraints
- 1 ≤ T ≤ 100.
- 0 ≤ R - L ≤ 10^5.
Hint
For the first sample, look at every possible number in the range [5, 10].
- 5: Alice paints 2 tiles, {1, 5}, and Bob paints no tile. The absolute difference is 2, so the game is interesting.
- 6: Alice paints 2 tiles, {1, 3}, and Bob paints 2 tiles, {2, 6}. The absolute difference is 0, so the game is interesting.
- 7: Alice paints 2 tiles, {1, 7}, and Bob paints no tile. The absolute difference is 2, so the game is interesting.
- 8: Alice paints 1 tile, {1}, and Bob paints 3 tiles, {2, 4, 8}. The absolute difference is 2, so the game is interesting.
- 9: Alice paints 2 tiles, {1, 3, 9}, and Bob paints no tile. The absolute difference is greater than 2, so the game is not interesting.
- 10: Alice paints 2 tiles, {1, 5}, and Bob paints 2 tiles, {2, 10}. The absolute difference is 0, so the game is interesting.
Thus, the answer for this test case is 5.
The second sample has only one number, 102. Alice paints 4 tiles, {1, 3, 17, 51}, while Bob paints 4 tiles, {2, 6, 34, 102}. The absolute difference is 0, so the game is interesting.