You are not logged in. Please login at www.codechef.com to post your questions!

×

modulus operator

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?

asked 16 Jun '17, 13:11

rishup_nitdgp's gravatar image

4★rishup_nitdgp
434
accept rate: 0%

1

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

(16 Jun '17, 14:28) hikarico5★

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.

(16 Jun '17, 15:33) rishup_nitdgp4★
1

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

(16 Jun '17, 15:46) hikarico5★

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)

link

answered 16 Jun '17, 14:37

dragonemperor's gravatar image

3★dragonemperor
89321134
accept rate: 10%

edited 16 Jun '17, 16:29

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.

(16 Jun '17, 15:25) rishup_nitdgp4★
2

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

(16 Jun '17, 15:44) hikarico5★

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

(16 Jun '17, 15:55) dragonemperor3★
link

answered 16 Jun '17, 16:04

hruday968's gravatar image

4★hruday968
1.7k210
accept rate: 14%

edited 16 Jun '17, 16:04

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×334

question asked: 16 Jun '17, 13:11

question was seen: 481 times

last updated: 16 Jun '17, 16:29