## Modular Calculator |

Back to Problem Solutions forum

transingularity
2015-06-30 15:17:35

Hi, I am trying to solve task #14 but i don't understand when I should find mod in algorythm. Here Rodion post the explanation:

```
(A * B + C * D * (E + F)) % M = ?
((A * B) % M + C * (D % M) * (E + F)) % M
```

I understood that if the number is so big it should be devided on *M* (or am I wrong again?). If I think right then how can I understand if the number is so big? Where is the limit?
Should I use *integers* here or *longs*?

Or is here another rule I can't get?

Here is my output (first steps) when I tried to devide on M every second multiplication, but the number didn't get less, it just got bigger:

```
+990 *8910 *%(1)21829500 +21832267 *109423322204 +109423330552 *328269991656 +328269991665
```

It went through positive infinity and then through negative :D

Thank you for help.

Sorry for such an essay and my stupidity :(

If you use % properly you don't need to use long as there is a small number of operations, the numbers are small, and M is of similar size to the others.

A % M gives a result from 0 .. M - 1.

Rodion's explanation shows two properties of % :

(A + B) % M = (A % M + B % M) % M

(A * B) % M = (A % M * B % M) % M

What does that tell you about when you can do % M ? When is it *worth* doing % M ? If you wait too long
you hit the integer limit quite quickly and it goes negative as you've seen.

Hope that helps.

OldProgrammer has the correct (best) answer.

If your language supports it, you can also use BigInteger or other large "language native" types. To solve the problem, I used .Net's "Decimal" type (max value = 79228162514264337593543950335) and learned *nothing* from the problem. :)

Thank you for asnwers :)

So I need to calculate mod for every single number I get? For example:

```
5 + 3 * 7 + 10 * 2 * 3 + 1 % 11
```

Will be

```
(5%11 + 3%11 * 7%11 + 10%11 * 2%11 * 3%11 + 1%11) % 11
```

:(

Or should I calculate mod only when the sum or multiplication is bigger than *M*?

**Edited:** I solved it with BigInteger on Java. But I really want to understand how to solve it with just *Int*. Even when I tried to calculate mod for every number it just never wants to calculate it.

You have a program that should not be difficult to change to answer your questions.

could someone plz advise why thos code dont read last line of input?

import java.util.Scanner; public class CAModularCalculator {

```
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
// char sign;
// int value;
long n = keyboard.nextLong();
System.out.println();
System.out.println(n);
while (keyboard.hasNext()) {
String line = keyboard.nextLine();
System.out.println(line);
//sign = line.charAt(0);
//value = Integer.parseInt((line.substring(2, line.length()-1)));
//System.out.println(sign + " " + value);
}
keyboard.close();
}
```

}

Hi,

When I try your code with the "Test Data" it prints

```
5+ 3* 7+ 10* 2* 3+ 1% 11
```

so it is reading the last line of input.

Please login and solve 5 problems to be able to post at forum