khanaleemullah's blog

modulo problem please help me..
By khanaleemullah, 11 years ago, In English

please help me friends.. i want to multpliy a number say x=100000 and y=100000 ; and the result is to be modulo by 1000000007. how should i approach to this i tried everything ...

  • Vote: I like it
  • -8
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Haven't you tried 8-bytes data types? Something like result = (long long) x * y % 1000000007

→ Reply
»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

"i tried everything"

:D:D:D:D

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

i think there is no problem with that since x and y are quite small number. just do it straightforward (x*y)%1000000007 . remember use long long in C++. if x and y are too big , you may consider this identity : (a*b)%c = (a%c * b%c )%c . CMIIW

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Also, if you need to multiply some realy big numbers (say x=1e15, y=1e17), and mod is something like 1e18, you may use this idea:

mult(a,b)%c=mult(a*2%c,b/2)%c for even b

and

mult(a,b)%c=(mult(a,b-1)%c+a)%c for odd b.

It's easy to implement recursively.

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can youse BIGMOD

→ Reply