《算法競賽進階指南》0x01 T2 64位整數乘法

題目傳送門

題目描述

求 a a a乘 b b b對 p p p取模的值。

輸入格式

第一行輸入整數 a a a，第二行輸入整數 b b b，第三行輸入整數 p p p。

輸出格式

輸出一個整數，表示 a ∗ b m o d p a*b mod p a∗bmodp的值。

資料範圍

1 ≤ a , b , p ≤ 1 0 18 1≤a,b,p≤10^{18} 1≤a,b,p≤1018

輸入樣例

3

4

5

輸出樣例

2

基礎硬體

取模運算

快速幂的優化過程

題解

這道題和之前寫過的0x01快速幂非常的相似

首先看這道題的資料範圍

如果直接用 O ( 1 ) O(1) O(1)的乘法去計算，最多能乘出來1e36的數，明顯是不可做的（當然可以用高精）

但這道題并不是這麼簡單，還有一個需要取模得數p

利用這個數，我們就可以在運算過程中不斷使用取模運算

使結果不會超過long long的範圍

是以！

隻需要在快速幂的基礎上改掉一些細節即可

題外話：雖然這個算法因為與快速幂相似而被稱作快速乘，但它其實是龜速乘，能用O1的算法何必瞎搞呢

code

#include<bits/stdc++.h>
using namespace std;
long long a,b,p;
long long Times(long long a,long long b) 
{
    long long result=0;
    while(b>0) 
 {
        if(b&1) result=(result+a)%p; //b&1等價于b%2==1 
        b>>=1; //power>>=1等價于power=power/2
        a=(a*2)%p;
    }
    return result%p;
}
int main()
{
    cin>>a>>b>>p;
    cout<<Times(a,b);
    return 0;
}