Keli365

Appearance

数论入门 - 快速幂 ​

一、课程目标 ​

  1. 幂问题
  2. 快速幂模板
  3. 大数溢出问题

二、目标详解 ​

1、幂问题 ​

指形如 a^b 的求解问题，例如 2^5 = 32。

a、b 都是正整数，a 称之为底数，b 称之为指数。

朴素解法就是循环 b 次，每次乘以 a。

c++
  int ans = 1;
  for(int i=1; i<=b; i++)
    ans *= a;

朴素解法问题：19^999999999 无法解决，算法需要改进！如何改进，使用快速幂！

  • 二进制分解回顾（除2取余法）
    1. 初始化：设要转换的正整数为 ( n )，初始的二进制字符串为空。
    2. 重复以下步骤直到 ( n ) 变为0：
      • 将 ( n ) 除以2，得到商 ( q ) 和余数 ( r )。
      • 将余数 ( r ) 添加到二进制字符串的最前面。
      • 更新 ( n ) 为商 ( q )。
    3. 最终结果：得到的二进制字符串即为 ( n ) 的二进制表示。

    示例： ​

    假设我们要将十进制数 13 转换为二进制：
    1. ( 13 / 2 = 6 ) 余 1
    2. ( 6 / 2 = 3 ) 余 0
    3. ( 3 / 2 = 1 ) 余 1
    4. ( 1 / 2 = 0 ) 余 1 将余数从下往上排列，得到二进制数：1101。

2、快速幂模板 ​

考虑b的二进制分解，例如13=2^3+2^2+2^0 = 1101（二进制）。

则a^13 = a^(8+4+1) = a^8 * a^4 * a^1。

思路：从二进制的个位数开始，如果系数为1（即二进制位是1），表示结果要乘以a^x，x是第几位。

算法模板：

c++
  int ans = 1;
  while(b) {
    if(b%2==1) ans *= a;//结果乘以a^x
    a *= a;  //a连乘x位
    b /= 2; //b二进制数往前
  }

3、大数溢出问题 ​

溢出：假设int a, b，a * b可能会超出int的范围，变成负数。

一般对于很大的结果，试题会给出一个大的模数P（例如10^9+7），结果对这个数求余。

  • 模运算分配律讲解

    模运算的分配律（Modular Multiplicative Distributive Law），也称作模乘法的同余性质。具体来说，对于整数a、b和正整数k，以下等式成立：

    (a * b) % k = ((a % k) * (b % k)) % k

    这个性质说明，在进行模k的乘法运算时，可以先对乘数取模，然后再相乘，最后的结果再取模，得到的结果与直接相乘后取模的结果是相同的。

    证明： ​

    1. 展开等式右边：
      • 设 a % k = r1 和 b % k = r2，即 a = k * m + r1 和 b = k * n + r2，其中m和n是整数，且 0 ≤ r1, r2 < k。
      • 则 (a % k) * (b % k) % k = r1 * r2 % k。
    2. 展开等式左边：
      • a * b = (k * m + r1) * (k * n + r2)
      • 展开得：a * b = k^2 * m * n + k * m * r2 + k * n * r1 + r1 * r2
      • 取模k：(a * b) % k = (k^2 * m * n + k * m * r2 + k * n * r1 + r1 * r2) % k
      • 由于 k^2 * m * n、k * m * r2 和 k * n * r1 都是k的倍数，它们取模k的结果为0。
      • 因此：(a * b) % k = r1 * r2 % k
    3. 结论：
      • 由此可见，(a * b) % k = ((a % k) * (b % k)) % k 成立。

    应用： ​

    这个性质在计算大数的乘积时非常有用，特别是当直接计算乘积会导致溢出或者效率低下时。通过先取模再相乘，可以有效避免这些问题。

    模运算其他的常见规律：

    • 模运算的结合律：对于任意整数a, b, c和正整数p，有((a + b) % p) + c % p = (a + (b + c) % p) % p。
    • 模运算的交换律：对于任意整数a, b和正整数p，有(a + b) % p = (b + a) % p。
    • 模运算的幂运算性质：对于任意整数a, b和正整数p，有(a ** b) % p = ((a % p) ** b) % p。
    • 模运算的重要定理：若a ≡ b (mod p)，则对于任意的c，都有 (a + c) ≡ (b + c) (mod p)，(a * c) ≡ (b * c) (mod p)。

可在每一步运算之后，就对P求余，例如(朴素幂算法)：

c++
  int ans = 1;
  for(int i=1; i<=b; i++)
    ans = (ans*a)%P; 朴素幂算法求余

但这样做还会有问题，就是ans * a溢出为负数。

可在运算的时候暂时转换为long long，防止int溢出。

c++
  int ans = 1;
  for(int i=1; i<=b; i++)
    ans = (1LL * ans * a)%P;

同样，快速幂的求余版本如下：

c++
int quick_pow(int a, int b) {
  int ans = 1;
  while(b) {
    if(b%2==1) ans = (1LL*ans*a)%MOD;
    a = (1LL*a*a)%MOD;
    b /= 2;
  } 
  return ans;
}

问题：

快速幂的时间复杂度是多少？

习题

P1412. 快速幂 ​

演示-快速幂模板 ​

一、实验目标 ​

输入两个正整数a和b，求a^b，结果可能很大，对10^9+7求余。

输入样例1：

c++
2 3

输出样例1：

c++
8

输入样例2：

c++
988 10

输出样例2：

c++
218386848

数据范围：

  • 40%：a <= 10, b<=8
  • 100%：a、b都是正整数
c++
#include <iostream>
using namespace std;

const int MOD=1e9+7;
long long a, b;

int quick_pow(int a, int b) {
  int ans = 1;
  while(b) {
    if(b%2==1) ans = (1LL*ans*a)%MOD;
    a = (1LL*a*a)%MOD;
    b /= 2;
  } 
  return ans;
}

int main() {
  cin>>a>>b;
  cout<<quick_pow(a, b)<<endl;
  return 0;
}

/*
#include <iostream>
using namespace std;
const int MOD=1e9+7;

long long a, b, ans = 1;
int main() {
  cin>>a>>b;
  for(int i=1; i<=b; i++)
    ans = (ans*a)%MOD;
  cout<<ans;
  return 0;
}

*/

练习-指数求余 ​

一、实验目标

输入b、p、k的值，求b^p mod k的值，b、p、k均为正整数。

输入样例：

2 10 9

输出样例：

7

c++
#include <iostream>
using namespace std;
int main() {
  long long a, b, k, ans;
  cin >> a >> b >> k;
  ans = 1;
  while (b) {
    if (b%2==1) ans = ans * a % k;
    a = a * a % k;
    b /= 2;
  }
  cout << ans;
  return 0;
}

Copyright © 2024 Keli365