b430. 簡單乘法 - 高中生程式解題系統

Content

背景

在早期密碼世界中，各種運算都先講求速度，不管是在硬體、軟體利用各種數學定義來設計加密算法就為了加快幾倍的速度，但在近代加密中，加速方法會造成硬體實作攻擊，速度和安全，你選擇哪一個呢。

$$a b \equiv x \mod n$$

已知 $a, b, n$，求出 $x$。

Input

有多組測資，每一組測資一行三個整數 $a, b, n$，其中 $0 \le a, b \le 10^{18}, 1 \le n \le 10^{18}$。

Output

對於每一組測資輸出一行，$ab \mod n$ 的結果。

Sample Input #1

Sample Output #1

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (100%): 1.0s , <10M

Hint ：

避免使用大數運算，利用加法代替乘法，使其不超過 64-bits，可參考 wiki Modular arithmetic 。

又或者利用 128-bits long double 型態來解決。

Tags:

大數快速冪運算數論基礎模數

出處:

[管理者：

morris1028 (碼畜) ]