TheDivisionGame | Topcoder Archive

Problem Statement

Manao likes to play the Division Game with his friends. This two-player game is played with some collection of natural numbers S. Manao plays first and the players alternate in making a move. A move is choosing some number X from S and a natural number Y &gt 1 such that Y divides X. Then, X is replaced by X / Y in the collection. Note that at any moment the collection may contain multiple copies of the same number. The game proceeds until no more moves can be made. The player who managed to make the last move is declared the winner.

Since hot debates arise on what numbers should be in S, the friends decided to regularize their choice. They always choose a contiguous interval of numbers [A, B] to be the initial collection S. That is, at the beginning of the game, the collection S contains each of the integers A through B, inclusive, exactly once. Manao knows that A and B will satisfy the condition L &le A &le B &le R. You are given the ints L and R. Count the number of such intervals for which Manao will win the Division Game given that both players play optimally.

Definition

Class:: TheDivisionGame
Method:: countWinningIntervals
Parameters:: int, int
Returns:: long
Method signature:: long countWinningIntervals(int L, int R)
(be sure your method is public)

Notes

Only one number from the collection changes in each move. For example, if the collection contains three copies of the number 8, and the player chooses X=8 and Y=4, only one of the 8s in the collection will change to a 2.

Constraints

L will be between 2 and 1,000,000,000, inclusive.
R will be between L and L + 1,000,000, inclusive.

Examples

```
9
```
```
10
```
```
Returns: 2
```
If the chosen interval is [9,9] or [10,10], the collection S contains only one number. In these two situations Manao can win the game in a single move. On the other hand, if the chosen interval is [9,10], Manao will lose to an optimally playing opponent.
```
2
```
```
5
```
```
Returns: 9
```
The only case where Manao loses is if the game starts with the interval [2,3]. Note that if the starting interval is [2,5], Manao can choose X=4 and Y=2 in his first move. After that move, the collection will contain the values 2, 2, 3, and 5.
```
2
```
```
6
```
```
Returns: 13
```
Manao will also lose the game if the starting interval is [3,6].
```
2
```
```
100
```
```
Returns: 4345
```
```
12566125
```
```
12567777
```
```
Returns: 1313432
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.