b430. 簡單乘法
標籤 : 大數 快速冪運算 數論基礎 模數
通過比率 : 283人/483人 ( 59% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-08-07 08:51

內容

背景

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

題目描述

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

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

輸入說明
有多組測資,每一組測資一行三個整數 $a, b, n$,其中 $0 \le a, b \le 10^{18}, 1 \le n \le 10^{18}$。
輸出說明
對於每一組測資輸出一行,$ab \mod n$ 的結果。
範例輸入 #1
3 5 7
2 4 3
2 0 2
5 1 4
範例輸出 #1
1
2
0
1
測資資訊:
記憶體限制: 64 MB
提示 :

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

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

標籤:
大數 快速冪運算 數論基礎 模數
出處:
[管理者: morris1028 (碼畜) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
25607 810416@fhsh. ... (Eric_hung) b430
1006 2021-06-06 17:05
24940 asnewchien@g ... (david) b430
python 分享
777 2021-04-06 22:20