Multiply Mod M
Computer Mathematics
Hard
2 views
Problem Description
Compute (a*b) mod m for up to 10^18 (use bigint idea).
Input Format
Three integers a b m.
Output Format
One integer.
Sample Test Case
Input:
1000000000000 1000000000000 97
Official Solution
Use repeated doubling (binary multiplication): result=0; while b>0 if bit set add a; a=(a*2)%m; b=floor(b/2).
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!