快速幂AcWing 89. a^b

求 $a$ 的 $b$ 次方对 $p$ 取模的值。

输入格式

三个整数 $a,b,p$ ,在同一行用空格隔开。

输出格式

输出一个整数，表示a^b mod p的值。

数据范围

$0 \le a,b \le 10^9$
$1 \le p \le 10^9$

输入样例：

3 2 7

输出样例：

2

快速计算$a^k\mod p$

• 实际上是把$k$表示成二进制$b_{\text{log}k}\cdots b_2b_1b_0$，因此$k=b_02^{2^0} + b_12^{2^1}+b_22^{2^2}+ \cdots b_{\text{log}k} 2^{2^{\text{log}k}}$
• 计算$a^k \mod p=a^{b_02^{2^0} + b_12^{2^1}+b_22^{2^2}+ \cdots b_{\text{log}k} 2^{2^{\text{log}k}}} \mod p=(a^{b_0 2^{2^0}}\mod p) \times (a^{b_1 2^{2^1}}\mod p) \times \cdots \times (a^{b_{\text{log}k} 2^{2^{\text{log}k}}}\mod p)$
• 此外迭代满足如下关系$2^{2^{i+1}} \mod p=(2^{2^{i}} \mod p)^2$
• 中间结果可能会溢出，要强制进行类型转换
• 时间复杂度$O(\text{log}k)$

$a^{b_i}=a×a×…×a$,暴力的计算需要O(n)的时间
快速幂使用二进制拆分和倍增思想，仅需要O(Iog)的时间。
对n做二进制拆分，例如，$3^{13}=3^{(1101)_2}=3^8·3^4·3^1$
对Q做平方倍增，例如，$3^1,3^2,3^4,3^8…$
n有logn+1个二进制位，我知道了$a^l,a^2,a^4,a^8,,a^{2logn}$后
只需要计算logn+1次乘法就可以了。

这里偷懒就用define int long long 了

代码

#include <bits/stdc++.h>

#define int long long
using namespace std;

int qmi(int x, int k, int p) {
    int res = 1;
    while (k) {
        if (k & 1) res = res * x % p;
        x = x * x % p;
        k >>= 1;
    }
    return res % p;
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int a, b, p;
    cin >> a >> b >> p;
    cout << qmi(a, b, p) << endl;
    return 0;
}

龟速乘AcWing 90. 64位整数乘法

题目

https://www.acwing.com/problem/content/description/92/

求 $a$ 乘 $b$ 对 $p$ 取模的值。

输入格式

第一行输入整数$a$，第二行输入整数$b$，第三行输入整数$p$。

输出格式

输出一个整数，表示a*b mod p的值。

数据范围

$1 \le a,b,p \le 10^{18}$

输入样例：

3
4
5

输出样例：

2

思路

与快速幂的思想一样，把乘法里面的b用二进制拆分，然后变成b个a相加

此外，还可以使用int128进行计算，但是需要注意强制类型转换

代码

#include <bits/stdc++.h>

#define int long long
using namespace std;

int mul(int a, int b, int p) {
    int res = 0;
    while (b) {
        if (b & 1) res = (res + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
    return res;
}

int mul2(int a, int b, int p) {
    __int128 aa = a, bb = b, pp = p;
    __int128 res = aa * bb % pp;
    return (int) res;
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    int a, b, p;
    cin >> a >> b >> p;
    cout << mul2(a, b, p);

    return 0;
}