解題區/解題區 - Zerojudge

b430. 簡單乘法

contents

  1. 1. Problem
    1. 1.1. 背景
    2. 1.2. 題目描述
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

背景

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

題目描述

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

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

Sample Input

1
2
3
4
3 5 7
2 4 3
2 0 2
5 1 4

Sample Output

1
2
3
4
1
2
0
1

Solution

利用加法代替乘法避免溢位，加法取模換成減法加快速度。

由於這一題範圍在在 $10^{18}$，用 long long 型態沒有問題，若在 $2^{63}$ 請替換成 unsigned long long。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h> 
using namespace std;
long long mul(long long a, long long b, long long mod) { 
    long long ret = 0; 
    for (a %= mod, b %= mod; b != 0; b>>=1, a <<= 1, a = a >= mod ? a - mod : a) { 
        if (b&1) {
            ret += a;
            if (ret >= mod) 
                ret -= mod;
        } 
    } 
    return ret; 
}
int main() {
    long long a, b, n;
    while (scanf("%lld %lld %lld", &a, &b, &n) == 3)
        printf("%lld\n", mul(a, b, n));
    return 0;
}