modulus operator

general
1

can somebody explain me that how modulus operator works and if i have two integer of value equal to 10^100 each then how i find the product with the help of inverse modulo?

2

can you give us a little more background of the problem?

1 Like
3

Can you please elaborate your question?

From what I understood, you need to find the product of two numbers modulo another number. If so, what is the size of modulo? I mean can it fit in integer (or long long) data type? If not, I suggest you to use bigInteger arithmetic (present in java, not C/C++). If it can fit, then the problem is really simple.

remember the following formula for modular arithmetic.

(a * b) M = ((a M) * (b M) ) M

(a + b) M = ((a M) + (b M) ) M

(a - b) M = ((a M) - (b M) ) M

(a / b) M = ((a M) * ((b^(M-2)) M) ) M //Provided M is prime

a^b M = {(a M) ^ (b (M-1)) } M //provided M is prime (thanks to @hikarico for suggesting)

Now coming to your problem,

you need to find product modulo M, i.e. (a * b) % M

As you mentioned, the size of a and b can be upto 10^100 which means we cannot store it in any datatype (overflow issue). So we can take the input as a string. Since M can be accommodated in pre-defined data types, a % M will be smaller than M, it can be accommodated in pre-defined datatype. So the problem reduces to, finding a%M and b%M and store them in some int (or long long) variable. Then we can simply apply our formula.

Now, let’s come to the HOW TO part. Look at the below number

12345

We can write it as :

1 * 10^4 + 2 * 10^3 + 3 * 10^2 + 4 * 10 + 5

which is equal to

5 + 10 * 4 + 10^2 * 3 + 10^3 * 2 + 10^4 * 1

which is equal to

5 + 10 * (4 + 10 * (3 + 10 * (2 + 10 * 1)))

now, this above figure modulo M can be found using the formulas

5 + 10 * (4 + 10 * (3 + 10 * (2 + 10 * 1))) % M

= (5 M) + ( 10 M * ( 4 M + 10 M * ( …

Hope this part is clear.

now since input is string, ASCII value of each number is stored. So a % M would be calculated as follows


long long ans;
len = strlen(a);  //a as string
for(i = 0; i < len; i++)
{
    ans = ans * 10 + (a[i] - '0');
    ans = ans % M;
}

Let me know if something is not clear or if this was not your question (in which case please clarify your question)

2 Likes
4

thanks. i was facing very difficulty to solve problem related to modulus operator but your answer is very elaborative and helpful. it helps me to solve my problem and now i think that i know about it. thanks again.

5

actually i want to find out the product of an array elements and constraint is i want to give my answer in terms of inverse modulo. the array size is 10^5 and value of each element of array does not grater than 10^9.

6

a^b % M = {(a % M) ^ (b % (M-1)) } % M works only if M is prime as well. Otherwise, it’s ((a % M)^(b % phi(M))) % M where phi is the euler totient function

2 Likes
7

I believe this tutorial on mod inverse can help you :slight_smile:

1 Like
8

Thank you. I didn’t know that. In all the problems I have solved, M was always prime in case of exponentiation.

9

here you can learn some powerful tricks with modulo