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

×

BIG_Answer % 100000007 Type problems

Hi guys , I want to know how to solve this type of problem. Suppose my result is going out of bound of integer and double then how to change my answer to Answer % 100000007.

Ex - (factorial(500)) % 1000000007

Most of the programming contest has this type of problem but I don't know the concept :( Please help.

asked 19 Nov '14, 15:07

theshubhamgoel's gravatar image

3★theshubhamgoel
718111925
accept rate: 5%

edited 19 Nov '14, 15:26

Probably you meant 109+7...

(19 Nov '14, 15:20) betlista ♦♦3★

Preface:

All such solution are based on few simple rules:

( a + b ) mod m = ( a mod n + b mod n ) mod n
( a * b ) mod m = ( a mod n * b mod n ) mod n

With negative numbers there is a problem - http://ideone.com/LmWJva according to wikipedia this is 3, not -2, so before doing minus operation it is recommended to add n (which is removed after mod operation), abs() is not working !!!

( a - b ) mod m = ( a mod n + n - b mod n ) mod n

What most of contestants are confused about is:

int MOD = 1000_000_007;
int a = 1000_000;
int b = 1000_000;
int c = ( a * b ) % MOD;

and while c is lower than MOD and a nad b are ints, it seems ok to use ints, but it is not...

Overflow occurs for a * b command.

Example - http://ideone.com/OUBGvs notice the result is negative.

There are few tricks how to overcome this

  1. use 1L * a * b
  2. or to use bigger type, long in Java, long long in C/C++ not long !!!

Disadvantage of 1.) is, that you have to identify all places where you need to apply this. And also you one have to know very well what is he doing - see http://ideone.com/IuyPDt

It may seem like there is problem with multiply only and addition is ok, there is a catch also:

a + b = ( a + b ) mod M

the above is fine for a,b <= 109 which it typical in problem statements...

But there is a problem if one tries to do

a + b + c = ( a + b + c ) mod M // there is overflow again - http://ideone.com/1glKK6

You may be interested also in this answer.

Few problems I searched quickly:

  1. LUCKY2
  2. TAPALIN

Note: see the 1000_000, this is valid 106 in Java >= 7 and I love it, for more examples see SO, it is also possible to write binary numbers as 0b1011 which is 11 in decimal...

link

answered 19 Nov '14, 15:15

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
accept rate: 11%

edited 19 Nov '14, 15:59

Thanks @betlista but i am talking about (factorial(100)) % 100000007 where the result can't be store even in double.

(19 Nov '14, 15:24) theshubhamgoel3★

while factorial n! = n * (n-1) * ... 2 * 1 ... it is very the same, you just need to us modulo for each multiplication, like this:

int res = 1;
for ( int i = 2; i <= n; ++i ) res = ( res * i ) % MOD;
(19 Nov '14, 15:26) betlista ♦♦3★

are u trying to say that 7%7 ==2%7 +5%7

I mean in some place if there is addition or other type of expression like power operator than can we apply this technique please help..

(19 Nov '14, 15:32) theshubhamgoel3★

Yes, power is the very the same as factorial x^n = n * n * ... * n I added rules above, from which this is derived...

(19 Nov '14, 15:38) betlista ♦♦3★

Thanks @betlista . One more thing

what about (n!/m!)%c =? and n and m >100

(20 Nov '14, 10:20) theshubhamgoel3★

this is more difficult, if you are interested in combinations (n!/(r! * (n-r)!), then there is excellent article about the topic, otherwise there is another article

(20 Nov '14, 12:27) betlista ♦♦3★
showing 5 of 6 show all

You can refer this blog by abhinav92003 on handling operators with mod. Also few concepts involving modular operations are well explained there.

Also @betlista has made a point where many contestants tend make a mistake.

link

answered 19 Nov '14, 15:25

vinayawsm's gravatar image

4★vinayawsm
1.9k21430
accept rate: 24%

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:

×2,738
×1,285
×348
×100

question asked: 19 Nov '14, 15:07

question was seen: 6,567 times

last updated: 20 Nov '14, 12:27