C++快速幂与大数取模算法示例

C++快速幂与大数取模算法示例

本文主要介绍C++中实现快速幂算法和大数取模算法的示例以及相关代码。快速幂算法可以很好地解决指数较大的幂运算问题,大数取模算法则可以在计算过程中避免数值过大而发生的溢出错误。

快速幂算法原理

快速幂算法是指通过对指数进行二进制分解后,根据分解结果按照乘幂的顺序计算幂运算结果。其本质上是一种分治策略,可以大大减少指数较大情况下的计算次数。

举例来说,如果要计算$x^y$,其中$y$的二进制表示为$b_k2^k+b_{k-1}2^{k-1}+...+b_12^1+b_02^0$,则可以按照如下方式进行计算:

  1. 初始化计算结果$res=1$;
  2. 从高位到低位依次遍历二进制表示,当遍历到$b_k$时进行如下操作:
  3. $res \leftarrow res \times res$;
  4. 如果$b_k=1$,则进行$res \leftarrow res \times x$的操作;
  5. 遍历结束,返回计算结果$res$。

通过上述方法,可以将计算指数为$y$的幂的时间复杂度降低至$O(log_2 y)$级别。

大数取模算法原理

大数取模算法是指通过一定的数学方法,在运算过程中不直接对大数进行运算,而是不断对大数取模得到小数后再进行运算,并最终取模得到最终结果。其本质原理是利用取模运算对数值的抑制作用,可以避免浮点数以及整数过大而引发的误差。

常用的大数取模算法有如下两种:

  1. Barrett约减算法。其基本思想是对大数进行规约,使其取模结果不超过另一个已知较小的数$m$,从而避免数值过大带来的误差。Barrett约减算法的时间复杂度为$O(n^2)$,其中$n$为大数的长度。
  2. 快速取模算法。快速取模算法则是一种基于快速幂算法的取模算法,可以快速地对大数进行取模,从而避免数值过大带来的误差。快速取模算法的时间复杂度为$O(nlog_2 n)$。

C++示例

下面给出C++中实现快速幂算法和大数取模算法的示例代码。

快速幂算法示例

以下示例展示了如何使用C++实现快速幂算法:

long long qmi(long long a, int b) {
    long long res = 1;
    while (b) {
        if (b & 1) res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}

上述代码通过右移运算符和按位与运算符来实现二进制位的判断和移动,从而实现了快速幂算法的计算。

快速幂取模示例

以下示例展示了如何使用快速幂算法进行大数取模:

long long qmi_mod(long long a, int b, int p) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

上述代码实现了快速幂算法与取模运算的结合,其中$p$为取模的模数。

Barrett约减示例

以下示例展示了如何使用C++实现Barrett约减算法:

struct Barrett {
    int m;
    int k; // 2k >= ceil(logb(m))
    long long r0; // 运算中的临时变量
    Barrett(int _m) : m(_m) {
        k = ceil(log2(m));
        r0 = qmi(10, 2 * k) / m + 1;
    }
    int reduce(long long x) { // 将x规约至[0, m)
        long long q = ((long long)r0 * x) >> 2 * k;
        long long r = x - q * m;
        return r < m ? r : r - m;
    }
};

上述代码利用了C++中的结构体和重载运算符的特性,通过C++的内置计算函数ceillog2qmi来实现Barrett约减算法的计算。

快速取模示例

以下示例展示了如何使用快速幂算法进行快速取模:

long long qmi_mod_2(long long a, int b, int p) {
    long long res = 1;
    while (b) {
        if (b & 1) res = (res * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return res;
}
int fast_mod(int a, int b, int p) {
    return qmi_mod_2(a, b % (p - 1), p);
}

上述代码通过对指数取模,从而将幂次数降低至$p-1$以内,利用快速幂算法进行计算,并最终再次对结果进行取模以得到最终结果。

以上就是对C++快速幂与大数取模算法示例的详细讲解。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C++快速幂与大数取模算法示例 - Python技术站

(0)
上一篇 2023年5月22日
下一篇 2023年5月22日

相关文章

  • C语言中如何进行异常处理?

    在C语言中,异常处理使用的是C语言标准库中的setjmp/longjmp函数。 setjmp函数设置一个返回点,并返回0,然后在任何时候,longjmp可以回到这个返回点并返回一个指定的值,这可以用来实现异常处理。 下面就是一个简单的例子: #include <stdio.h> #include <setjmp.h> jmp_buf …

    C 2023年4月27日
    00
  • C++生成和解析XML文件的讲解

    下面是关于C++生成和解析XML文件的攻略。 生成XML文件 1. 引入头文件 XML文件的生成需要用到tinyxml2这个开源库。因此首先需要下载此库,并在代码中引入相应的头文件。 #include <tinyxml2.h> 2. 创建根节点 在生成XML文件之前,需要先创建一个根节点。可以使用tinyxml2库提供的XMLDocument类来…

    C 2023年5月23日
    00
  • 适合初学者练习的C语言实现三子棋小游戏

    适合初学者练习的C语言实现三子棋小游戏完整攻略 三子棋是一款简单的棋盘游戏,它的规则简单易懂,被广泛地应用于人机交互、智力测试等领域。下面是如何使用C语言实现三子棋小游戏的完整攻略: 步骤一:确定游戏规则 首先,我们需要确定游戏规则,确保实现的游戏规则正确,符合三子棋的规则,如: 游戏双方执黑子和白子 执黑子先走 棋盘为3 x 3 的方格状 玩家操作后棋子不…

    C 2023年5月23日
    00
  • 如何利用C++实现mysql数据库的连接池详解

    如何利用C++实现mysql数据库的连接池详解 什么是数据库连接池 数据库连接池是一种用来缓存数据库连接的技术,它可以提高数据库的访问效率,避免重复连接数据库导致的资源浪费和性能下降。在高并发的情况下,数据库连接池会发挥更大的优势。 如何利用C++实现mysql数据库的连接池 1. 安装mysql C++ Connector mysql C++ Connec…

    C 2023年5月22日
    00
  • C语言如何实现一些算法或者函数你知道吗

    针对“C语言如何实现一些算法或者函数”这个问题,我可以提供以下攻略: 一、理解算法和函数的概念 在开始实现算法和函数之前,需要先理解算法和函数的概念。 算法:算法是指解决问题的方法和步骤。在编程中,算法是一组逐步执行的指令,用于解决特定问题。 函数:函数是一段封装了特定功能的代码块,可重复使用。在C语言中,函数必须先被声明,然后才能被调用。 二、挑选算法或函…

    C 2023年5月23日
    00
  • Visual C++ 6.0无法正常启动提示0xc0000142怎么办?vc6.0无法执行程序解决方法

    Visual C++ 6.0无法正常启动提示0xc0000142怎么办? 当你在使用 Visual C++ 6.0 运行程序时,可能会遇到“无法正常启动,错误代码为 0xc0000142”的提示信息。出现这个问题的原因多种多样,可能是操作系统或 Visual C++ 本身的问题。下面我们来一步步解决这个问题。 步骤一:升级 Visual C++ 6.0 首先…

    C 2023年5月23日
    00
  • 使用vs2010编译log4cxx图文教程

    使用vs2010编译log4cxx图文教程: 步骤1:下载并解压log4cxx库 首先去Apache网站下载log4cxx的源码包,例如: https://downloads.apache.org/logging/log4cxx/0.11.0/apache-log4cxx-0.11.0.tar.gz 解压后得到一个apache-log4cxx-0.11.0的…

    C 2023年5月23日
    00
  • C语言实现二叉树的基本操作

    C语言实现二叉树的基本操作 一、概述 二叉树是一种经典的数据结构,它是由若干个节点构成的树形结构,每个节点最多有两个子节点(左子节点和右子节点)。在C语言中,二叉树的实现可以使用结构体和指针来完成。本文将详细介绍如何实现二叉树的基本操作。 二、数据结构 二叉树的数据结构可以使用以下结构体来定义: typedef struct TreeNode { int d…

    C 2023年5月23日
    00
合作推广
合作推广
分享本页
返回顶部