Statistics

Problem Statement for "RandomGCD"

Problem Statement

Consider the integers between low and high, inclusive. We are going to select a sequence of N integers from this range. The sequence is allowed to contain repeated elements, hence there are (high-low+1)^N possible sequences (where '^' denotes exponentiation).

Out of those sequences, we are only interested in the ones that have one additional property: the greatest common divisor (GCD) of their elements must be exactly K.

You are given the ints N, K, low, and high. Let X be the number of N-tuples described above. Because X can be very large, compute and return the value (X modulo 1,000,000,007).

Definition

Class:
RandomGCD
Method:
countTuples
Parameters:
int, int, int, int
Returns:
int
Method signature:
int countTuples(int N, int K, int low, int high)
(be sure your method is public)

Notes

  • The greatest common divisor of a sequence is the largest positive integer that divides each element of the sequence.

Constraints

  • N, K and low will each be between 1 and 1,000,000,000, inclusive.
  • high will be between low and 1,000,000,000, inclusive.
  • The difference high - low will be less than or equal to 100,000.

Examples

  1. 2

    2

    2

    4

    Returns: 3

    There are 9 possible sequences: {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4), (4, 2), (4, 3), (4, 4)}. Out of these, 3 of them have the requested gcd of 2: {(2, 2), (2, 4), (4, 2)}. Hence, the answer is 3.

  2. 2

    100

    2

    4

    Returns: 0

    Sometimes no combinations yield the requested GCD.

  3. 1

    5

    5

    5

    Returns: 1

    Sometimes you select only one number.

  4. 73824

    17347

    9293482

    9313482

    Returns: 0

  5. 222

    222

    222

    22222

    Returns: 339886855

  6. 1

    1000000000

    1000000000

    1000000000

    Returns: 1

  7. 10

    1000000000

    1000000000

    1000000000

    Returns: 1

  8. 1

    1

    5

    5

    Returns: 0

  9. 10

    1

    1000000000

    1000000000

    Returns: 0

  10. 1

    1

    1

    3

    Returns: 1

  11. 1

    2

    1

    3

    Returns: 1

  12. 1

    3

    1

    3

    Returns: 1

  13. 1

    4

    1

    3

    Returns: 0

  14. 2

    1

    1

    3

    Returns: 7

  15. 3

    1

    1

    3

    Returns: 25

  16. 4

    1

    1

    3

    Returns: 79

  17. 5

    1

    1

    3

    Returns: 241

  18. 6

    1

    1

    3

    Returns: 727

  19. 7

    1

    1

    3

    Returns: 2185

  20. 8

    1

    1

    3

    Returns: 6559

  21. 9

    1

    1

    3

    Returns: 19681

  22. 10

    1

    1

    3

    Returns: 59047

  23. 10

    2

    1

    3

    Returns: 1

  24. 10

    3

    1

    3

    Returns: 1

  25. 10

    4

    1

    3

    Returns: 0

  26. 1

    1

    5

    7

    Returns: 0

  27. 1

    2

    5

    7

    Returns: 0

  28. 1

    3

    5

    7

    Returns: 0

  29. 1

    4

    5

    7

    Returns: 0

  30. 1

    5

    5

    7

    Returns: 1

  31. 1

    6

    5

    7

    Returns: 1

  32. 1

    7

    5

    7

    Returns: 1

  33. 2

    1

    5

    7

    Returns: 6

  34. 2

    2

    5

    7

    Returns: 0

  35. 2

    3

    5

    7

    Returns: 0

  36. 2

    4

    5

    7

    Returns: 0

  37. 2

    5

    5

    7

    Returns: 1

  38. 2

    6

    5

    7

    Returns: 1

  39. 2

    7

    5

    7

    Returns: 1

  40. 10

    1

    5

    7

    Returns: 59046

  41. 10

    2

    5

    7

    Returns: 0

  42. 10

    3

    5

    7

    Returns: 0

  43. 10

    4

    5

    7

    Returns: 0

  44. 10

    5

    5

    7

    Returns: 1

  45. 10

    6

    5

    7

    Returns: 1

  46. 10

    7

    5

    7

    Returns: 1

  47. 317283918

    1

    5

    7

    Returns: 721061157

  48. 317283918

    2

    5

    7

    Returns: 0

  49. 317283918

    3

    5

    7

    Returns: 0

  50. 317283918

    4

    5

    7

    Returns: 0

  51. 317283918

    5

    5

    7

    Returns: 1

  52. 317283918

    6

    5

    7

    Returns: 1

  53. 317283918

    7

    5

    7

    Returns: 1

  54. 3

    1

    6

    8

    Returns: 18

  55. 3

    2

    6

    8

    Returns: 6

  56. 3

    3

    6

    8

    Returns: 0

  57. 3

    4

    6

    8

    Returns: 0

  58. 3

    5

    6

    8

    Returns: 0

  59. 3

    6

    6

    8

    Returns: 1

  60. 3

    7

    6

    8

    Returns: 1

  61. 3

    8

    6

    8

    Returns: 1

  62. 9

    1

    6

    8

    Returns: 19170

  63. 9

    2

    6

    8

    Returns: 510

  64. 9

    3

    6

    8

    Returns: 0

  65. 9

    4

    6

    8

    Returns: 0

  66. 9

    5

    6

    8

    Returns: 0

  67. 9

    6

    6

    8

    Returns: 1

  68. 9

    7

    6

    8

    Returns: 1

  69. 9

    8

    6

    8

    Returns: 1

  70. 999999999

    1

    6

    8

    Returns: 841667386

  71. 999999999

    2

    6

    8

    Returns: 570312502

  72. 999999999

    3

    6

    8

    Returns: 0

  73. 999999999

    4

    6

    8

    Returns: 0

  74. 999999999

    5

    6

    8

    Returns: 0

  75. 999999999

    6

    6

    8

    Returns: 1

  76. 999999999

    7

    6

    8

    Returns: 1

  77. 999999999

    8

    6

    8

    Returns: 1

  78. 2

    5

    500000

    500005

    Returns: 2

  79. 2

    5

    500001

    500006

    Returns: 0

  80. 2

    5

    500002

    500007

    Returns: 0

  81. 2

    5

    500003

    500008

    Returns: 0

  82. 2

    5

    500004

    500009

    Returns: 0

  83. 2

    5

    500005

    500010

    Returns: 2

  84. 2

    4

    500000

    500005

    Returns: 2

  85. 2

    4

    500001

    500006

    Returns: 0

  86. 2

    4

    500002

    500007

    Returns: 0

  87. 2

    4

    500003

    500008

    Returns: 2

  88. 2

    4

    500004

    500009

    Returns: 2

  89. 2

    4

    500005

    500010

    Returns: 0

  90. 536870912

    5

    500000

    500005

    Returns: 915398905

  91. 536870912

    5

    500001

    500006

    Returns: 0

  92. 536870912

    5

    500002

    500007

    Returns: 0

  93. 536870912

    5

    500003

    500008

    Returns: 0

  94. 536870912

    5

    500004

    500009

    Returns: 0

  95. 536870913

    5

    500005

    500010

    Returns: 830797805

  96. 536870912

    4

    500000

    500005

    Returns: 915398905

  97. 536870912

    4

    500001

    500006

    Returns: 0

  98. 536870912

    4

    500002

    500007

    Returns: 0

  99. 536870912

    4

    500003

    500008

    Returns: 915398905

  100. 536870912

    4

    500004

    500009

    Returns: 915398905

  101. 536870911

    4

    500005

    500010

    Returns: 0

  102. 1000000000

    1

    999900000

    1000000000

    Returns: 48567676

  103. 1000000000

    2

    999900000

    1000000000

    Returns: 403668037

  104. 1000000000

    3

    999900000

    1000000000

    Returns: 381774275

  105. 1000000000

    4

    999900000

    1000000000

    Returns: 259071306

  106. 1000000000

    5

    999900000

    1000000000

    Returns: 353167927

  107. 1000000000

    6

    999900000

    1000000000

    Returns: 964430985

  108. 1000000000

    7

    999900000

    1000000000

    Returns: 385441380

  109. 1000000000

    30

    999900000

    1000000000

    Returns: 326508394

  110. 1000000000

    210

    999900000

    1000000000

    Returns: 10574025

  111. 1000000000

    2310

    999900000

    1000000000

    Returns: 294016436

  112. 1000000000

    30030

    999900000

    1000000000

    Returns: 486572269

  113. 1000000000

    510510

    999900000

    1000000000

    Returns: 0

  114. 1000000000

    65536

    999900000

    1000000000

    Returns: 0

  115. 1000000000

    93312

    999900000

    1000000000

    Returns: 0

  116. 2

    99013

    999900000

    1000000000

    Returns: 0

  117. 1000000000

    99013

    999900000

    1000000000

    Returns: 0

  118. 1000000000

    99999

    999900000

    1000000000

    Returns: 0

  119. 1000000000

    100000

    999900000

    1000000000

    Returns: 140624999

  120. 1000000000

    100001

    999900000

    1000000000

    Returns: 0

  121. 1000000000

    999900017

    999900000

    1000000000

    Returns: 1

  122. 10

    1

    50000

    150000

    Returns: 840328261

  123. 10

    2

    50000

    150000

    Returns: 890475777

  124. 10

    3

    50000

    150000

    Returns: 895228182

  125. 10

    4

    50000

    150000

    Returns: 955539639

  126. 10

    5

    50000

    150000

    Returns: 551803675

  127. 10

    6

    50000

    150000

    Returns: 847652868

  128. 10

    7

    50000

    150000

    Returns: 865822130

  129. 10

    30

    50000

    150000

    Returns: 355214186

  130. 10

    210

    50000

    150000

    Returns: 36094273

  131. 10

    2310

    50000

    150000

    Returns: 133068654

  132. 10

    30030

    50000

    150000

    Returns: 58024

  133. 10

    65536

    50000

    150000

    Returns: 1023

  134. 10

    93312

    50000

    150000

    Returns: 1

  135. 10

    99013

    50000

    150000

    Returns: 1

  136. 10

    50021

    50000

    150000

    Returns: 1023

  137. 10

    100042

    50000

    150000

    Returns: 1

  138. 10

    86436

    50000

    150000

    Returns: 1

  139. 999999999

    1

    50000

    150000

    Returns: 100788028

  140. 999999999

    2

    50000

    150000

    Returns: 778471692

  141. 999999999

    3

    50000

    150000

    Returns: 476985055

  142. 999999999

    4

    50000

    150000

    Returns: 695395362

  143. 999999999

    5

    50000

    150000

    Returns: 117590804

  144. 999999999

    6

    50000

    150000

    Returns: 773819981

  145. 999999999

    7

    50000

    150000

    Returns: 197470516

  146. 999999999

    30

    50000

    150000

    Returns: 660956018

  147. 999999999

    210

    50000

    150000

    Returns: 312327741

  148. 999999999

    2310

    50000

    150000

    Returns: 284844490

  149. 999999999

    30030

    50000

    150000

    Returns: 841667386

  150. 999999999

    65536

    50000

    150000

    Returns: 570312503

  151. 999999999

    93312

    50000

    150000

    Returns: 1

  152. 999999999

    99013

    50000

    150000

    Returns: 1

  153. 999999999

    50021

    50000

    150000

    Returns: 570312503

  154. 999999999

    100042

    50000

    150000

    Returns: 1

  155. 999999999

    86436

    50000

    150000

    Returns: 1

  156. 2

    1

    999999999

    1000000000

    Returns: 2

  157. 2

    2

    999999999

    1000000000

    Returns: 0

  158. 2

    3

    999999999

    1000000000

    Returns: 0

  159. 2

    999999998

    999999999

    1000000000

    Returns: 0

  160. 2

    999999999

    999999999

    1000000000

    Returns: 1

  161. 2

    1000000000

    999999999

    1000000000

    Returns: 1

  162. 7

    1

    999999999

    1000000000

    Returns: 126

  163. 7

    2

    999999999

    1000000000

    Returns: 0

  164. 7

    3

    999999999

    1000000000

    Returns: 0

  165. 7

    999999998

    999999999

    1000000000

    Returns: 0

  166. 7

    999999999

    999999999

    1000000000

    Returns: 1

  167. 7

    1000000000

    999999999

    1000000000

    Returns: 1

  168. 8

    1

    999950000

    999950884

    Returns: 202425809

  169. 8

    2

    999950000

    999950884

    Returns: 108046841

  170. 8

    6

    999950000

    999950884

    Returns: 535186198

  171. 8

    7

    999950000

    999950884

    Returns: 456598822

  172. 8

    9

    999950000

    999950884

    Returns: 643190829

  173. 8

    81

    999950000

    999950884

    Returns: 212613728

  174. 8

    91

    999950000

    999950884

    Returns: 99602558

  175. 3

    883

    999950000

    999950884

    Returns: 0

  176. 3

    884

    999950000

    999950884

    Returns: 0

  177. 3

    885

    999950000

    999950884

    Returns: 0

  178. 3

    886

    999950000

    999950884

    Returns: 0

  179. 3

    999950000

    999950000

    999950884

    Returns: 1

  180. 3

    999950884

    999950000

    999950884

    Returns: 1

  181. 8

    1

    999950000

    999950885

    Returns: 125112855

  182. 8

    2

    999950000

    999950885

    Returns: 108046841

  183. 8

    6

    999950000

    999950885

    Returns: 535186198

  184. 8

    7

    999950000

    999950885

    Returns: 456598822

  185. 8

    9

    999950000

    999950885

    Returns: 643190829

  186. 8

    81

    999950000

    999950885

    Returns: 212613728

  187. 8

    91

    999950000

    999950885

    Returns: 99602558

  188. 3

    883

    999950000

    999950885

    Returns: 0

  189. 3

    884

    999950000

    999950885

    Returns: 0

  190. 3

    885

    999950000

    999950885

    Returns: 0

  191. 3

    886

    999950000

    999950885

    Returns: 0

  192. 3

    999950000

    999950000

    999950885

    Returns: 1

  193. 3

    999950884

    999950000

    999950885

    Returns: 1

  194. 8

    1

    999950000

    999950883

    Returns: 151709307

  195. 8

    2

    999950000

    999950883

    Returns: 575321905

  196. 8

    6

    999950000

    999950883

    Returns: 535186198

  197. 8

    7

    999950000

    999950883

    Returns: 456598822

  198. 8

    9

    999950000

    999950883

    Returns: 643190829

  199. 8

    81

    999950000

    999950883

    Returns: 212613728

  200. 8

    91

    999950000

    999950883

    Returns: 99602558

  201. 3

    883

    999950000

    999950883

    Returns: 0

  202. 3

    884

    999950000

    999950883

    Returns: 0

  203. 3

    885

    999950000

    999950883

    Returns: 0

  204. 3

    886

    999950000

    999950883

    Returns: 0

  205. 3

    999950000

    999950000

    999950883

    Returns: 1

  206. 3

    999950883

    999950000

    999950883

    Returns: 1

  207. 2

    1

    100

    100000

    Returns: 67220906

  208. 2

    2

    100

    100000

    Returns: 516822319

  209. 2

    3

    100

    100000

    Returns: 674124662

  210. 2

    4

    100

    100000

    Returns: 379221086

  211. 2

    5

    100

    100000

    Returns: 242698098

  212. 2

    50

    100

    100000

    Returns: 2429176

  213. 2

    97

    100

    100000

    Returns: 643004

  214. 2

    99

    100

    100000

    Returns: 618648

  215. 2

    500

    100

    100000

    Returns: 24463

  216. 2

    2310

    100

    100000

    Returns: 1167

  217. 2

    30030

    100

    100000

    Returns: 7

  218. 2

    256

    100

    100000

    Returns: 92599

  219. 2

    729

    100

    100000

    Returns: 11539

  220. 2

    1296

    100

    100000

    Returns: 3663

  221. 2

    4444

    100

    100000

    Returns: 299

  222. 2

    2401

    100

    100000

    Returns: 1059

  223. 2

    2379

    100

    100000

    Returns: 1083

  224. 2

    2380

    100

    100000

    Returns: 1083

  225. 2

    2381

    100

    100000

    Returns: 1059

  226. 2

    2382

    100

    100000

    Returns: 1059

  227. 1024

    1

    100

    100000

    Returns: 293324133

  228. 1024

    2

    100

    100000

    Returns: 809536930

  229. 1024

    3

    100

    100000

    Returns: 697578672

  230. 1024

    4

    100

    100000

    Returns: 648533613

  231. 1024

    5

    100

    100000

    Returns: 694318151

  232. 1024

    50

    100

    100000

    Returns: 942734933

  233. 1024

    97

    100

    100000

    Returns: 693721243

  234. 1024

    99

    100

    100000

    Returns: 306077921

  235. 1024

    500

    100

    100000

    Returns: 699708703

  236. 1024

    2310

    100

    100000

    Returns: 188815965

  237. 1024

    30030

    100

    100000

    Returns: 763327762

  238. 1024

    256

    100

    100000

    Returns: 754857330

  239. 1024

    729

    100

    100000

    Returns: 940966834

  240. 1024

    1296

    100

    100000

    Returns: 827594391

  241. 1024

    4444

    100

    100000

    Returns: 109710277

  242. 1024

    2401

    100

    100000

    Returns: 860873642

  243. 1024

    2379

    100

    100000

    Returns: 60642699

  244. 1024

    2380

    100

    100000

    Returns: 60642699

  245. 1024

    2381

    100

    100000

    Returns: 860873642

  246. 1024

    2382

    100

    100000

    Returns: 860873642

  247. 2538743

    1

    1

    100000

    Returns: 640656050

  248. 2538743

    2

    1

    100000

    Returns: 119251277

  249. 2538743

    3

    1

    100000

    Returns: 48516904

  250. 2538743

    4

    1

    100000

    Returns: 568839576

  251. 2538743

    5

    1

    100000

    Returns: 719689702

  252. 2538743

    6

    1

    100000

    Returns: 638836358

  253. 2538743

    7

    1

    100000

    Returns: 171668667

  254. 2538743

    8

    1

    100000

    Returns: 851020166

  255. 2538743

    9

    1

    100000

    Returns: 932829476

  256. 2538743

    10

    1

    100000

    Returns: 876170141

  257. 2538743

    1

    2

    100000

    Returns: 280223885

  258. 2538743

    2

    2

    100000

    Returns: 119251277

  259. 2538743

    3

    2

    100000

    Returns: 48516904

  260. 2538743

    4

    2

    100000

    Returns: 568839576

  261. 2538743

    5

    2

    100000

    Returns: 719689702

  262. 2538743

    6

    2

    100000

    Returns: 638836358

  263. 2538743

    7

    2

    100000

    Returns: 171668667

  264. 2538743

    8

    2

    100000

    Returns: 851020166

  265. 2538743

    9

    2

    100000

    Returns: 932829476

  266. 2538743

    10

    2

    100000

    Returns: 876170141

  267. 2538743

    1

    3

    100000

    Returns: 700872213

  268. 2538743

    2

    3

    100000

    Returns: 29183350

  269. 2538743

    3

    3

    100000

    Returns: 48516904

  270. 2538743

    4

    3

    100000

    Returns: 568839576

  271. 2538743

    5

    3

    100000

    Returns: 719689702

  272. 2538743

    6

    3

    100000

    Returns: 638836358

  273. 2538743

    7

    3

    100000

    Returns: 171668667

  274. 2538743

    8

    3

    100000

    Returns: 851020166

  275. 2538743

    9

    3

    100000

    Returns: 932829476

  276. 2538743

    10

    3

    100000

    Returns: 876170141

  277. 1023

    1

    25200

    50399

    Returns: 325954539

  278. 1023

    1

    25200

    50400

    Returns: 299278702

  279. 1023

    1

    25200

    50401

    Returns: 731030817

  280. 1023

    1

    25199

    50399

    Returns: 90222059

  281. 1023

    1

    25199

    50400

    Returns: 331248360

  282. 1023

    1

    25199

    50401

    Returns: 694391321

  283. 1023

    1

    25201

    50399

    Returns: 783362771

  284. 1023

    1

    25201

    50400

    Returns: 325954539

  285. 1023

    1

    25201

    50401

    Returns: 490004516

  286. 1023

    2

    25200

    50399

    Returns: 719654258

  287. 1023

    2

    25200

    50400

    Returns: 145580949

  288. 1023

    2

    25200

    50401

    Returns: 145580949

  289. 1023

    2

    25199

    50399

    Returns: 719654258

  290. 1023

    2

    25199

    50400

    Returns: 145580949

  291. 1023

    2

    25199

    50401

    Returns: 145580949

  292. 1023

    2

    25201

    50399

    Returns: 974264681

  293. 1023

    2

    25201

    50400

    Returns: 719654258

  294. 1023

    2

    25201

    50401

    Returns: 719654258

  295. 1023

    3

    25200

    50399

    Returns: 148170220

  296. 1023

    3

    25200

    50400

    Returns: 532647052

  297. 1023

    3

    25200

    50401

    Returns: 532647052

  298. 1023

    3

    25199

    50399

    Returns: 148170220

  299. 1023

    3

    25199

    50400

    Returns: 532647052

  300. 1023

    3

    25199

    50401

    Returns: 532647052

  301. 1023

    3

    25201

    50399

    Returns: 997960663

  302. 1023

    3

    25201

    50400

    Returns: 148170220

  303. 1023

    3

    25201

    50401

    Returns: 148170220

  304. 1023

    4

    25200

    50399

    Returns: 340495199

  305. 1023

    4

    25200

    50400

    Returns: 461835982

  306. 1023

    4

    25200

    50401

    Returns: 461835982

  307. 1023

    4

    25199

    50399

    Returns: 340495199

  308. 1023

    4

    25199

    50400

    Returns: 461835982

  309. 1023

    4

    25199

    50401

    Returns: 461835982

  310. 1023

    4

    25201

    50399

    Returns: 688862377

  311. 1023

    4

    25201

    50400

    Returns: 340495199

  312. 1023

    4

    25201

    50401

    Returns: 340495199

  313. 1023

    5

    25200

    50399

    Returns: 606551619

  314. 1023

    5

    25200

    50400

    Returns: 376415493

  315. 1023

    5

    25200

    50401

    Returns: 376415493

  316. 1023

    5

    25199

    50399

    Returns: 606551619

  317. 1023

    5

    25199

    50400

    Returns: 376415493

  318. 1023

    5

    25199

    50401

    Returns: 376415493

  319. 1023

    5

    25201

    50399

    Returns: 905363744

  320. 1023

    5

    25201

    50400

    Returns: 606551619

  321. 1023

    5

    25201

    50401

    Returns: 606551619

  322. 1023

    7

    25200

    50399

    Returns: 962180710

  323. 1023

    7

    25200

    50400

    Returns: 726728675

  324. 1023

    7

    25200

    50401

    Returns: 726728675

  325. 1023

    7

    25199

    50399

    Returns: 962180710

  326. 1023

    7

    25199

    50400

    Returns: 726728675

  327. 1023

    7

    25199

    50401

    Returns: 726728675

  328. 1023

    7

    25201

    50399

    Returns: 892436384

  329. 1023

    7

    25201

    50400

    Returns: 962180710

  330. 1023

    7

    25201

    50401

    Returns: 962180710

  331. 1023

    50

    25200

    50399

    Returns: 219392355

  332. 1023

    50

    25200

    50400

    Returns: 488175693

  333. 1023

    50

    25200

    50401

    Returns: 488175693

  334. 1023

    50

    25199

    50399

    Returns: 219392355

  335. 1023

    50

    25199

    50400

    Returns: 488175693

  336. 1023

    50

    25199

    50401

    Returns: 488175693

  337. 1023

    50

    25201

    50399

    Returns: 890185386

  338. 1023

    50

    25201

    50400

    Returns: 219392355

  339. 1023

    50

    25201

    50401

    Returns: 219392355

  340. 1023

    70

    25200

    50399

    Returns: 23651591

  341. 1023

    70

    25200

    50400

    Returns: 607677615

  342. 1023

    70

    25200

    50401

    Returns: 607677615

  343. 1023

    70

    25199

    50399

    Returns: 23651591

  344. 1023

    70

    25199

    50400

    Returns: 607677615

  345. 1023

    70

    25199

    50401

    Returns: 607677615

  346. 1023

    70

    25201

    50399

    Returns: 13044936

  347. 1023

    70

    25201

    50400

    Returns: 23651591

  348. 1023

    70

    25201

    50401

    Returns: 23651591

  349. 1000000000

    1

    10000009

    10100009

    Returns: 589462748

  350. 100000

    1

    999900000

    1000000000

    Returns: 788218420

  351. 999999999

    1

    999900000

    1000000000

    Returns: 303965228

  352. 999999999

    2

    888888

    979999

    Returns: 640786751

  353. 1000000000

    1

    999990000

    1000000000

    Returns: 31731028

  354. 999173787

    211

    998134120

    998234117

    Returns: 64591866

  355. 999912345

    42

    921337666

    921437666

    Returns: 87757156

  356. 1000000000

    223092870

    1

    100000

    Returns: 0

  357. 1

    2

    3

    3

    Returns: 0

  358. 918392842

    1

    932905353

    932994818

    Returns: 871221436

  359. 100000

    2

    1000000

    1100000

    Returns: 117502210

  360. 1

    8

    8000006

    8000008

    Returns: 0

  361. 10000000

    1

    100000000

    100100000

    Returns: 69150140

  362. 1000

    1

    100001

    200000

    Returns: 630632444

  363. 1000000000

    1

    999989999

    1000000000

    Returns: 475772415

  364. 10

    1

    13847389

    13847389

    Returns: 0

  365. 1000000000

    2

    100000000

    100100000

    Returns: 650970404

  366. 4

    1

    999999937

    999999938

    Returns: 14

  367. 2

    1

    11000027

    11000027

    Returns: 0

  368. 50000

    1

    999900000

    1000000000

    Returns: 777822549

  369. 1000000000

    2

    999900001

    1000000000

    Returns: 631037809

  370. 100

    1

    1

    100000

    Returns: 286473656

  371. 888888888

    30

    555455556

    555555555

    Returns: 464242500

  372. 10

    1

    33333334

    33333335

    Returns: 1022

  373. 987654321

    1

    999900000

    1000000000

    Returns: 257473750

  374. 1000000000

    1

    1

    100000

    Returns: 408813909

  375. 100

    1

    999900000

    1000000000

    Returns: 760579244

  376. 1000000000

    1

    900000000

    900100000

    Returns: 336118142

  377. 2

    1

    11000026

    11000027

    Returns: 2

  378. 1

    3

    100

    102

    Returns: 0

  379. 1

    5

    900000000

    900100000

    Returns: 0

  380. 1000000000

    36

    10000

    100000

    Returns: 311848543

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: