Statistics

Problem Statement for "WrongBase"

Problem Statement

In this problem, some computations are done modulo 998,244,353. This number is a prime.

Alice had a positive integer g. This number had a special property: none of the numbers g499122176, g142606336 and g58720256 was congruent with 1 modulo 998,244,353.

Alice then chose n positive integers: x1, ..., xn. For each i, she computed the value yi = (gxi modulo 998,244,353). Surprisingly, it turned out to be the case that the values yi formed an arithmetic sequence with the first element a and difference d.

Bob does not like Alice's number g. Instead, he likes the number h. He would like to compute the values zi = (hxi modulo 998,244,353).

You are given the ints g, h, a, d, and n. Compute and return the sum of all Bob's values zi, modulo 998,244,353.

Definition

Class:
WrongBase
Method:
getSum
Parameters:
int, int, int, int, int
Returns:
int
Method signature:
int getSum(int g, int h, int a, int d, int n)
(be sure your method is public)

Notes

  • The return value always exists and it is always unique.

Constraints

  • g is an integer between 2 and 998244352, inclusive.
  • h is an integer between 0 and 998244352, inclusive.
  • a is an integer between 1 and 998244352, inclusive.
  • d is an integer between 1 and 998244352, inclusive.
  • n is an integer between 1 and 106, inclusive.
  • It is guaranteed that all n values of the arithmetic sequence that starts with a and has difference d are between 1 and 998244352, inclusive.
  • It is guaranteed that none of g499122176, g142606336 and g58720256 is congruent with 1 modulo 998244353.

Examples

  1. 3

    7

    3

    3

    5

    Returns: 754398841

    The sequence y equals [3, 6, 9, 12, 15], which corresponds to x = [1, 640079067, 2, 281913781, 109353320]. The answer is thus 71 + 7640079067 + 72 + 7281913781 + 7109353320 = 1752643194, which is congruent to 754398841 modulo 998244353.

  2. 1557

    1555

    1564

    1244

    567821

    Returns: 847300188

  3. 13

    1

    1

    1

    1000000

    Returns: 1000000

  4. 193

    0

    2

    25

    1000000

    Returns: 0

  5. 884

    884

    17

    12

    1000000

    Returns: 562438470

  6. 426211459

    152155823

    740238343

    1382

    94722

    Returns: 302704481

  7. 541214181

    973391311

    540012973

    726

    328033

    Returns: 10318166

  8. 283618403

    614179323

    419296285

    579

    893160

    Returns: 412536272

  9. 292809653

    57858373

    113677123

    1568

    542417

    Returns: 682832541

  10. 389210643

    185246021

    80351375

    573

    739011

    Returns: 928176650

  11. 931932715

    144239336

    291925398

    229

    821173

    Returns: 118910419

  12. 612916695

    717221833

    424307716

    382

    198021

    Returns: 786250019

  13. 265845828

    862523353

    821606241

    130

    794293

    Returns: 838930161

  14. 928347654

    889594744

    136104324

    20961

    32666

    Returns: 140054830

  15. 587154583

    816283799

    3799011

    1707

    291654

    Returns: 980044451

  16. 373205971

    764443913

    602287205

    1384

    115986

    Returns: 499012643

  17. 169392170

    70264549

    181360612

    325

    807258

    Returns: 913083753

  18. 775610575

    825004261

    471048384

    603

    703686

    Returns: 637219911

  19. 218010664

    60018648

    746872253

    27

    213454

    Returns: 94863778

  20. 211036769

    705620139

    352682676

    370

    546408

    Returns: 674274016

  21. 257507136

    518700592

    515034193

    649

    496776

    Returns: 414654590

  22. 708171703

    42440071

    591558146

    252

    965797

    Returns: 490758458

  23. 223560595

    979450596

    201257232

    473

    616742

    Returns: 374891161

  24. 929006305

    725119534

    197627958

    78

    265999

    Returns: 124573194

  25. 426867382

    65466400

    216268649

    269

    563865

    Returns: 533349751

  26. 310733067

    20613186

    198147286

    2503

    132849

    Returns: 650742974

  27. 488861401

    680685052

    33887895

    815

    892597

    Returns: 991586478

  28. 476622939

    124364102

    726513085

    161

    541854

    Returns: 982701313

  29. 592661947

    470835962

    683526697

    3234

    75246

    Returns: 110748366

  30. 362739379

    470479174

    306986064

    520

    732773

    Returns: 522103481

  31. 821084985

    421904426

    70529038

    337

    861325

    Returns: 188981707

  32. 861151321

    211594794

    925781788

    83

    826943

    Returns: 445968121

  33. 834925555

    543501684

    199167646

    2212

    292003

    Returns: 789743261

  34. 837610440

    877494530

    400613226

    344

    821939

    Returns: 211528

  35. 51813325

    35683899

    313374900

    367

    809157

    Returns: 567177153

  36. 11

    0

    123

    80

    1000000

    Returns: 0

  37. 3

    0

    3

    3

    5

    Returns: 0

  38. 3

    0

    2

    2

    2

    Returns: 0

  39. 3

    0

    1

    23

    1000000

    Returns: 0

  40. 3

    7

    3

    3

    1000000

    Returns: 903283165

  41. 998244341

    0

    1

    41

    1000000

    Returns: 0

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: