ModModMod | Topcoder Archive

Problem Statement

Moose Mod has just learned about the mod operator. Given two positive integers x and y, the mod operator returns the remainder when x is divided by y. For example, 17 mod 5 = 2 because 17 = 3*5 + 2.

Moose Mod has just defined a function that applies a sequence of N mod operators to its input. Formally, the function looks as follows: f(x) = (((x mod m[0]) mod m[1]) ... mod m[N-1]). For example, m = { 10, 3 } corresponds to the function f(x) = (x mod 10) mod 3. For this function we have f(18) = (18 mod 10) mod 3 = 8 mod 3 = 2.

You are given the int[] m. You are also given a int R. Moose Mod is interested in finding the sum f(1) + f(2) + ... + f(R). Compute and return its value.

Definition

Class:: ModModMod
Method:: findSum
Parameters:: int[], int
Returns:: long
Method signature:: long findSum(int[] m, int R)
(be sure your method is public)

Constraints

m will have between 1 and 5,000 elements, inclusive.
Each element of m will be between 1 and 10,000,000, inclusive.
R will be between 1 and 10,000,000, inclusive.

Examples

```
{5,3,2}
```
```
10
```
```
Returns: 4
```
The values of f from 1 to 10 are 1, 0, 0, 1, 0, 1, 0, 0, 1, 0. The sum of all these values is 4.
```
{33, 15, 7, 10, 100, 9, 5}
```
```
64
```
```
Returns: 92
```

{995,149,28,265,275,107,555,241,702,462,519,212,362,478,783,381,602,546,183,886,59,317,977,612,328,91,771,131}

Returns: 12792005

{100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100,
 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100}

Returns: 4950

```
{2934}
```
```
10000000
```
```
Returns: 14664070144
```

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.