Problem Solutions: Modular Calculator

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 :(

OldProgrammer 2015-06-30 23:13:41

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.

Guy Gervais 2015-06-30 23:25:16

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

transingularity 2015-07-01 07:42:03

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.

OldProgrammer 2015-07-01 09:01:35

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

BBaranyi 2016-12-22 15:57:10

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();
}

}

Quandray 2016-12-22 19:31:14

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.