Biết rằng (a * b)%c = ((a%c)*(b%c))%c, ví dụ: (10*3)%4 = 2 và (((10%4)*(3%4)))%4 = 6%4 = 2; trong khi đó giới hạn biểu diễn của long long là cỡ 18 chữ số, hãy tính (a*b)%c khi mà tích (a*b) có thể vượt quá khả năng biểu diễn của long long trong C++.
Trong bài này, số c có thể lên đến 1018, đây là một điều khá tệ vì sau khi % xong, ta nhân lại vẫn có thể tràn số. Để khắc phục điều này, bạn hãy tìm hiểu về phép nhân Ấn độ nhé! https://viblo.asia/p/phep-nhan-an-do-thuat-toan-binh-phuong-va-nhan-gDVK2dmrlLj
Yêu cầu: Tính (a * b)%c
Input:
- Dòng 1 chứa 2 số nguyên dương a và b (a,b<=1018);
- Dòng 2 ghi số nguyên dương c (c<=1018).
Output: (a * b)%c