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

×

# modulus operator

 0 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 43●4 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) 1 I believe this tutorial on mod inverse can help you :) (16 Jun '17, 15:46) hikarico5★

 2 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) answered 16 Jun '17, 14:37 893●2●11●34 accept rate: 10% 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) 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)
 0 here you can learn some powerful tricks with modulo https://www.hackerearth.com/practice/notes/powerful-tricks-with-calculation-modulo/ answered 16 Jun '17, 16:04 1.7k●2●10 accept rate: 14%
 toggle preview community wiki:
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