Connection Status:
Competition Arena > WrongBase

WrongBase

TCO19 SRM 751 · 2019-01-09 · by majk

TCO19 SRM 751 · 2019-01-09 · by majk · Math
Class Name: WrongBase
Return Type: int
Method Name: getSum
Arg Types: (int, int, int, int, int)
Problem Statement

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.

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
0)
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.

1)
1557
1555
1564
1244
567821
Returns: 847300188
2)
13
1
1
1
1000000
Returns: 1000000
3)
193
0
2
25
1000000
Returns: 0
4)
884
884
17
12
1000000
Returns: 562438470

Submissions are judged against all 41 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class WrongBase with a public method int getSum(int g, int h, int a, int d, int n) · 41 test cases · 2 s / 256 MB per case

Submitting as anonymous