MahdiJumping | Topcoder Archive

Problem Statement

Mahdi is playing a game in Quera.

In the beginning he is standing on position 0. His goal is to reach position n-1.

From any position x other than n-1, he can simply go to position x+1. Each such move costs a.

From any position x he can jump to position (A*x+B) mod n. Each such jump costs b.

Compute and return the minimal total cost of reaching the goal.

Definition

Class:: MahdiJumping
Method:: minDis
Parameters:: int, int, int, int, int
Returns:: long
Method signature:: long minDis(int n, int A, int B, int a, int b)
(be sure your method is public)

Constraints

n, A, a, and b will each be between 1 and 5,000,000, inclusive.
B will be between 0 and 5,000,000, inclusive.

Examples

```
7
```
```
1
```
```
1
```
```
1
```
```
5
```
```
Returns: 6
```
Mahdi will simply go to 1, 2, 3, 4, 5, 6.
```
5
```
```
2
```
```
2
```
```
1
```
```
2
```
```
Returns: 3
```
Mahdi will go to x = 1 and then to x = 4.
```
5
```
```
5
```
```
5
```
```
5
```
```
5
```
```
Returns: 20
```

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.