Statistics

Problem Statement for "TheDivisionGame"

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

  1. 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. 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.

  3. 2

    6

    Returns: 13

    Manao will also lose the game if the starting interval is [3,6].

  4. 2

    100

    Returns: 4345

  5. 2

    1000000

    Returns: 484332732439

  6. 999805519

    1000072678

    Returns: 34556370200

  7. 322182648

    322366988

    Returns: 16458568846

  8. 972332890

    972991678

    Returns: 210198241511

  9. 621951803

    622514232

    Returns: 153220984390

  10. 439994515

    440256601

    Returns: 33270043250

  11. 246393079

    247097102

    Returns: 240055105607

  12. 735723387

    735981106

    Returns: 32159046732

  13. 136622599

    137301388

    Returns: 223179003425

  14. 995729871

    995999472

    Returns: 35186785054

  15. 928521092

    929178016

    Returns: 209018892540

  16. 313049587

    313806848

    Returns: 277610201814

  17. 306324944

    306741607

    Returns: 84047562501

  18. 917527876

    918390177

    Returns: 360158429580

  19. 498758103

    499481464

    Returns: 253450583775

  20. 124459316

    125179275

    Returns: 251059459794

  21. 277598778

    278295907

    Returns: 235386888210

  22. 787264027

    787293044

    Returns: 406583323

  23. 452363613

    452697481

    Returns: 53987632578

  24. 513997053

    514233830

    Returns: 27145496229

  25. 519831547

    520505144

    Returns: 219777996483

  26. 963150948

    963191500

    Returns: 794716297

  27. 823418002

    824138375

    Returns: 251360267051

  28. 121125910

    121159002

    Returns: 530168251

  29. 304949729

    305059410

    Returns: 5795337874

  30. 581905907

    582132507

    Returns: 24769134983

  31. 690179303

    690871331

    Returns: 231936917782

  32. 498892693

    499771152

    Returns: 373788102163

  33. 739417415

    740072972

    Returns: 208101472766

  34. 59514906

    60026429

    Returns: 126730757152

  35. 15950270

    16496160

    Returns: 144341568064

  36. 1000000000

    1001000000

    Returns: 484283198296

  37. 1000000000

    1000999999

    Returns: 484282227087

  38. 999992337

    1000735125

    Returns: 267186927998

  39. 1769231

    2042041

    Returns: 35967574613

  40. 227633262

    228191236

    Returns: 150789097552

  41. 78813294

    79619929

    Returns: 315164873645

  42. 5532558

    6305121

    Returns: 289100669074

  43. 316885025

    317516761

    Returns: 193303790510

  44. 244051794

    244640881

    Returns: 168083555209

  45. 860698463

    861305104

    Returns: 178256637164

  46. 996513632

    996980625

    Returns: 105625900802

  47. 301279250

    301508496

    Returns: 25446777025

  48. 374189411

    374577316

    Returns: 72798202317

  49. 9236217

    9840769

    Returns: 177019805409

  50. 94047129

    94167616

    Returns: 7031495982

  51. 45187085

    45576001

    Returns: 73250601799

  52. 633980676

    634636864

    Returns: 208556568290

  53. 19576505

    20169081

    Returns: 169857904630

  54. 10038384

    10556001

    Returns: 129749022173

  55. 361707707

    361912576

    Returns: 20323479752

  56. 427665693

    428407204

    Returns: 266258283474

  57. 414586888

    415344400

    Returns: 277800445017

  58. 9969942

    10310521

    Returns: 56089594166

  59. 12566125

    12567777

    Returns: 1313432

  60. 999999888

    1000999888

    Returns: 484283199243

  61. 999000000

    1000000000

    Returns: 484361741725

  62. 1000000000

    1000900000

    Returns: 392269511489

  63. 999999999

    1000999333

    Returns: 483636599604

  64. 999000001

    1000000000

    Returns: 484360773690

  65. 900000000

    901000000

    Returns: 484204626300

  66. 101000001

    102000000

    Returns: 484227486489

  67. 724313112

    725313112

    Returns: 484374259067

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.
This problem was used for: