WrongBase | Topcoder Archive

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 g^499122176, g^142606336 and g^58720256 was congruent with 1 modulo 998,244,353.

Alice then chose n positive integers: x₁, ..., x_n. For each i, she computed the value y_i = (g^x_i modulo 998,244,353). Surprisingly, it turned out to be the case that the values y_i 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 z_i = (h^x_i 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 z_i, 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

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

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.