Multiply Mod M
Hard
Computer Mathematics
Modular Arithmetic
30 views
Problem Statement
Compute (a*b) mod m for up to 10^18 (use bigint idea).
Input Format
Three integers a b m.
Output Format
One integer.
Example
1000000000000 1000000000000 97
16
Constraints
m>0
Input / Output Format
Input Format
Three integers a b m.
Output Format
One integer.
Constraints
m>0
Examples
Input:
1000000000000 1000000000000 97
Output:
16
Example Solution (Public)
Use repeated doubling (binary multiplication): result=0; while b>0 if bit set add a; a=(a*2)%m; b=floor(b/2).
Official Solution Code
Use repeated doubling (binary multiplication): result=0; while b>0 if bit set add a; a=(a*2)%m; b=floor(b/2).
Please login to submit solutions.