Statistics

Problem Statement for "PolynomialRemainder"

Problem Statement

Cat Snuke received a polynomial P(x) = ax^2 + bx + c as a present. Now he is interested in finding a nonnegative integer y such that P(y) is divisible by one billion (10^9).

You are given three ints a, b, and c. Find an integer y between 0 and 999,999,999, inclusive, such that P(y) is divisible by one billion. If there are multiple solutions, return any. If there is no solution, return -1 instead.

Definition

Class:
PolynomialRemainder
Method:
findRoot
Parameters:
int, int, int
Returns:
int
Method signature:
int findRoot(int a, int b, int c)
(be sure your method is public)

Constraints

  • a, b, and c will be between 0 and 999,999,999, inclusive.

Examples

  1. 0

    0

    0

    Returns: 0

    P(x) = 0 for all x. Any integer between 0 and 999,999,999, inclusive, will be accepted.

  2. 0

    0

    1

    Returns: -1

    P(x) = 1 for all x, so there is no solution.

  3. 1

    2

    3

    Returns: -1

    We can prove that there is no solution in this case.

  4. 123456000

    789012345

    678901230

    Returns: 121618466

    P(x) = 123456000x^2 + 789012345x + 678901230. P(121618466) = 1826044121818350000000000.

  5. 479659453

    928595613

    143451144

    Returns: 647373336

  6. 397035859

    289524539

    485403580

    Returns: 61353099

  7. 664587627

    474703131

    762214376

    Returns: -1

  8. 568226500

    870969194

    923620667

    Returns: -1

  9. 580649521

    511688818

    886575430

    Returns: -1

  10. 205273790

    955621011

    748811040

    Returns: 797331360

  11. 24187291

    794786035

    296778200

    Returns: -1

  12. 4055675

    753626012

    995950118

    Returns: -1

  13. 791731198

    814823286

    54355988

    Returns: -1

  14. 200742480

    630015891

    293671351

    Returns: 409352259

  15. 56436519

    843728370

    943926465

    Returns: -1

  16. 743175238

    616432270

    923134689

    Returns: -1

  17. 722064508

    970806688

    285525111

    Returns: -1

  18. 701710629

    12117187

    788000849

    Returns: -1

  19. 154660458

    19622006

    287060055

    Returns: -1

  20. 866652967

    419335728

    730760543

    Returns: -1

  21. 46716653

    932359659

    878830965

    Returns: -1

  22. 63484204

    319155027

    718666245

    Returns: 258893365

  23. 815095973

    594872724

    142383283

    Returns: -1

  24. 14146120

    256006856

    620108755

    Returns: -1

  25. 152512737

    226200316

    345158147

    Returns: -1

  26. 803896553

    351130383

    663734824

    Returns: 227421928

  27. 966511952

    12731715

    957600394

    Returns: -1

  28. 41018964

    806615777

    320142640

    Returns: 153756880

  29. 85598013

    288420605

    885391414

    Returns: -1

  30. 391782117

    88909433

    297389953

    Returns: -1

  31. 923657703

    716501024

    157955159

    Returns: -1

  32. 595300708

    307250752

    948487294

    Returns: -1

  33. 896574010

    387049656

    535777268

    Returns: -1

  34. 499352137

    746162590

    4564886

    Returns: -1

  35. 501966299

    466181394

    200166104

    Returns: -1

  36. 561034996

    313671384

    128522048

    Returns: 59003944

  37. 28680206

    134570545

    740110196

    Returns: 391388268

  38. 125397091

    836421721

    925263308

    Returns: 143090761

  39. 199699873

    562195855

    19768222

    Returns: 347445314

  40. 54110566

    375671318

    648787940

    Returns: 15679057

  41. 41025349

    864982782

    889816125

    Returns: 58894857

  42. 301344822

    395693778

    944947616

    Returns: 152362117

  43. 879578642

    165548970

    902043472

    Returns: 434142392

  44. 595016638

    929245561

    743237871

    Returns: 365636187

  45. 405125058

    165933423

    265513975

    Returns: 274660425

  46. 677546903

    102899760

    563268937

    Returns: 333502151

  47. 17171146

    552615966

    606171384

    Returns: 142126092

  48. 960664401

    171440072

    959537996

    Returns: 3574334

  49. 96241930

    110216420

    770173040

    Returns: 35969562

  50. 914616949

    711489056

    46300067

    Returns: 933319827

  51. 109917771

    173451586

    58923744

    Returns: 4207632

  52. 632010414

    436100328

    134825818

    Returns: 330787341

  53. 926030782

    798478188

    44198998

    Returns: 55942673

  54. 458196070

    130683647

    613929074

    Returns: 811615818

  55. 364501855

    283510869

    830501846

    Returns: 254537046

  56. 591368688

    887703179

    87676283

    Returns: 22428511

  57. 685492444

    267982479

    293880552

    Returns: 14633576

  58. 316039259

    869830300

    469157369

    Returns: 645794947

  59. 518242835

    637865632

    759439220

    Returns: 363572290

  60. 148170679

    632431608

    992766900

    Returns: 516595798

  61. 642632540

    671651510

    3605360

    Returns: 1058008

  62. 699767804

    84511694

    902921022

    Returns: 5525173

  63. 60532153

    374332143

    122977094

    Returns: 764687978

  64. 872642999

    48286746

    216903715

    Returns: 587001435

  65. 294139195

    466889179

    300112816

    Returns: 90725616

  66. 0

    456789443

    872459689

    Returns: 477632477

  67. 0

    335978461

    976772966

    Returns: 535389794

  68. 0

    791813823

    827684392

    Returns: 773088296

  69. 0

    755104081

    15674713

    Returns: 370347127

  70. 0

    887335088

    89815630

    Returns: -1

  71. 0

    620827846

    770004650

    Returns: 120755225

  72. 0

    653465642

    494457562

    Returns: 864287239

  73. 0

    982516380

    589676486

    Returns: -1

  74. 0

    105822344

    90685076

    Returns: -1

  75. 0

    558203203

    974556800

    Returns: 830454400

  76. 120675000

    159925875

    924625000

    Returns: 1429000

  77. 457600000

    85156250

    323126750

    Returns: -1

  78. 320000000

    285300000

    422933600

    Returns: -1

  79. 587375000

    416600000

    46515000

    Returns: -1

  80. 235624348

    468800000

    276800000

    Returns: -1

  81. 324375000

    557812500

    927295960

    Returns: -1

  82. 450000000

    218750000

    578400000

    Returns: -1

  83. 809050000

    674332400

    642618912

    Returns: -1

  84. 263250000

    244800000

    856000000

    Returns: 161280

  85. 624480000

    916088000

    0

    Returns: 0

  86. 750000000

    105468750

    500000000

    Returns: 128

  87. 795841024

    166368625

    441600000

    Returns: -1

  88. 740000000

    296604800

    808403125

    Returns: -1

  89. 84044800

    217343750

    35556000

    Returns: -1

  90. 63511250

    558067200

    287500000

    Returns: 3562500

  91. 875000000

    739800000

    656085000

    Returns: -1

  92. 725000000

    207336000

    438300850

    Returns: -1

  93. 922656250

    724800000

    488750000

    Returns: -1

  94. 245312500

    631504875

    695836800

    Returns: -1

  95. 380800000

    628906250

    375000000

    Returns: 10400

  96. 600000000

    894625000

    63923000

    Returns: -1

  97. 475000000

    828687500

    556608000

    Returns: -1

  98. 920000000

    632633600

    509095125

    Returns: -1

  99. 812500000

    428181248

    29000000

    Returns: -1

  100. 575312500

    450900000

    858371875

    Returns: -1

  101. 330200000

    984375000

    0

    Returns: 0

  102. 118208000

    783280800

    174960000

    Returns: 2551300

  103. 509765625

    766400000

    884156250

    Returns: -1

  104. 682624000

    528500000

    305543280

    Returns: -1

  105. 833184000

    588374250

    343562500

    Returns: 5670598

  106. 566025120

    0

    365450240

    Returns: -1

  107. 12500000

    264843750

    398400000

    Returns: -1

  108. 685338752

    979374448

    579840000

    Returns: 161920000

  109. 790160640

    32041250

    701616000

    Returns: 10187840

  110. 844000000

    877172800

    843430800

    Returns: -1

  111. 187500000

    857888000

    319279000

    Returns: -1

  112. 193760000

    694800000

    343750000

    Returns: -1

  113. 500000000

    282190000

    0

    Returns: 0

  114. 843750000

    320000000

    467910625

    Returns: -1

  115. 875000000

    400000000

    8724830

    Returns: -1

  116. 869687500

    431863624

    139907793

    Returns: -1

  117. 276500000

    49548800

    63750000

    Returns: -1

  118. 43500000

    135000000

    278125000

    Returns: -1

  119. 652000000

    909723136

    230461696

    Returns: 462732289

  120. 123981000

    187500000

    671056800

    Returns: -1

  121. 452102800

    12000000

    443742000

    Returns: -1

  122. 531250000

    963095480

    150000000

    Returns: 138750000

  123. 828891000

    293120000

    875000000

    Returns: -1

  124. 112670720

    696087500

    125000000

    Returns: 170000

  125. 487744000

    127200000

    459552000

    Returns: -1

  126. 0

    1

    1

    Returns: 999999999

  127. 0

    999999999

    1

    Returns: 1

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: