1 / 8
Mar 2011

hi all

i have problem on working with mod operation on big numbers.

e.g
(a+b)%10000000007 where a and b are both unsigned long long in cpp

both a and b are near to LLONG_MAX.
value of both are being changed by some fixed operation like multiplication iteratively.

Now i am confused in following.is it right or not?
(a+b)%10000000007=a%10000000007+b%10000000007

and same thing with multiplication
(a*b)%10000000007=(a%10000000007)*(b%10000000007)

please help me in this concept.

With Regards
Jaini

No but You're close. smile
That's the correct formula:
(a+b)%10000000007=(a%10000000007+b%10000000007)%10000000007

Because assume that a=b=9999999999.
(a+b)%10000000007=19999999998%10000000007=9999999991
And a%10000000007+b%10000000007=a+b=19999999998

thanks for you answer smile

please tell me
can i use it to calculate 10 raise to power 18th fibonacci no. using following

matrix form

I may not understand.
The formula You've written allows You to calculate the next Fibonacci number.
The complexity is O(n), then (it anybody disagree please correct me).
I don't understand what does it have in common with "modulo trick" and 10-power.
Sorry for my ignorance if I don't know the algorithm You want to use.

actually i need to find out (nth fibonacci no.) % 10000000007 and that n can be 10^18.

sorry ,i wrote wrong formula i'm using following

F(x+2) (1 1)^x (1)
=
F(x+1) (1 0) (1)

understand it wrt matrix form(no good way to represent matrix here.. smile)

modulo trick is needed because matrix element would be multiplied and thus can go beyond maximum limit of LONG_MAX.

If You have to deal with so big numbers, is Your formula fast enought?
Because with this range of n even O(n) is too slow.

// I think FAQ isn't a good section for this kind of problems.