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

一、快速幂

其实就是求（a^b）% p ,（其中a,b,p都比较大在int范围内）这类问题。

首先要知道取余的公式： （a*b）%p=（a%p*b%p）%p 。

那么幂不就是乘机的累积吗，由此给出代码：

int fast(int a,int b,int p)

{  long long a1=a,t=1;

  while(b>0)  

  { if(b&1)     /如果幂b是奇数多乘一次，因为后边会除2变偶数，（7/2=3）

  t=(t%p)*(a1%p)%p;

  a1=(a1%p)*(a1%p)%p; 

  b/=2;  }

 return (int)(t%p);

}

二、大数取模

它的原理就是这个取余公式： （a+b）%p=(a%p+b%p)%p;

那么大数可以看做每一位的那位数字乘以自身的权然后每位相加。

如：12345678=（1*10000000）+（2*1000000）+…+8。

代码如下：

char s[200];

#define mod 10000010;

int main()

{  while(gets(s))

{  int k=strlen(s),sum=0;

 for(int i=0;i<k;i++)

 sum=(sum*10+s[i]-'0')%mod;  /当然要是担心sum还可能溢出，那就对里边再拆开来取余

 cout<<sum<<endl;

} }

三、总结

以上就是本文的全部内容，希望对大家的学习和工作能有所帮助。如果有疑问可以留言交流。

赞 (0)

相关推荐

  • C++实现的大数相乘算法示例

    本文实例讲述了C++实现的大数相乘算法.分享给大家供大家参考,具体如下: 昨晚校招笔试,虐的没脸睡觉,能力太渣了,但我还在码农的坑里前行,希望早日跳坑,解决衣食住行之忧. 大数相乘,是指那些相乘结果或是乘数本身用long long类型都会溢出的数字,通常这些数字都通过string类型进行表示,借助于可动态调整大小的数据结构(vector,string,deque)模拟实现数字的乘法操作.对于普通的乘法,我们知道m位数和n位数相乘,最后的结果位数在区间内[m+n-1,m+n].例如34*56,我们

  • C++实现大数乘法算法代码

    C++实现大数乘法算法代码 复制代码 代码如下: //大数乘法算法 #include<iostream> #include<string> #include<cstring> using namespace std; int main() {     string num1,num2;     cin >> num1 >> num2;     //cout << num1.size() << " " &

  • C++堆排序算法的实现方法

    C++堆排序算法的实现方法

    本文实例讲述了C++实现堆排序算法的方法,相信对于大家学习数据结构与算法会起到一定的帮助作用.具体内容如下: 首先,由于堆排序算法说起来比较长,所以在这里单独讲一下.堆排序是一种树形选择排序方法,它的特点是:在排序过程中,将L[n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲节点和孩子节点之间的内在关系,在当前无序区中选择关键字最大(或最小)的元素. 一.堆的定义 堆的定义如下:n个关键字序列L[n]成为堆,当且仅当该序列满足: ①L(i) <= L(2i)且L(i) <= L(2

  • C++选择排序算法实例

    选择排序 选择排序是一种简单直观的排序算法,它的工作原理如下.首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾.以此类推,直到所有元素均排序完毕. 选择排序的主要优点与数据移动有关.如果某个元素位于正确的最终位置上,则它不会被移动.选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换.在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常

  • c++二叉树的几种遍历算法

    1. 前序/中序/后序遍历(递归实现) 复制代码 代码如下: // 前序遍历void BT_PreOrder(BiTreePtr pNode){ if (!pNode)  return;    visit(pNode);   BT_PreOrder(pNode->left); BT_PreOrder(pNode->right);   }// 中序遍历void BT_PreOrder(BiTreePtr pNode){  if (!pNode)  return;     BT_PreOrder(

  • C++实现迷宫算法实例解析

    本文以实例形式描述了C++实现迷宫算法.本例中的迷宫是一个矩形区域,它有一个入口和一个出口.在迷宫的内部包含不能穿越的墙或障碍.障碍物沿着行和列放置,它们与迷宫的矩形边界平行.迷宫的入口在左上角,出口在右下角 本实例迷宫算法的功能主要有: 1.自动生成10*10迷宫图 2.判断是否有迷宫出口,并且画出路线图 具体实现代码如下: # include <iostream> # include <list> # include <sys/timeb.h> # include

  • C++实现简单遗传算法

    本文实例讲述了C++实现简单遗传算法.分享给大家供大家参考.具体实现方法如下: //遗传算法 GA #include<iostream> #include <cstdlib> #include<bitset> using namespace std; const int L=5; //定义编码的长度 int f(int x) //定义测设函数f(x) { int result; result=x*x*x-60*x*x+900*x+100; return result;

  • C++实现DES加密算法实例解析

    本文所述实例是一个实现DES加密算法的程序代码,在C++中,DES加密是比较常用的加密算法了,且应用非常广泛.本CPP类文件可满足你的DES加密需要,代码中附带了丰富的注释,相信对于大家理解DES可以起到很大的帮助. 具体实现代码如下: #include "memory.h" #include "stdio.h" enum {encrypt,decrypt};//ENCRYPT:加密,DECRYPT:解密 void des_run(char out[8],char

  • C++基本算法思想之穷举法

    C++基本算法思想之穷举法

    穷举算法(Exhaustive Attack method)是最简单的一种算法,其依赖于计算机的强大计算能力来穷尽每一种可能性,从而达到求解问题的目的.穷举算法效率不高,但是适应于一些没有规律可循的场合. 穷举算法基本思想穷举算法的基本思想就是从所有可能的情况中搜索正确的答案,其执行步骤如下: (1)对于一种可能的情况,计算其结果. (2)判断结果是否符合要求,如果不满足则执行第(1)步来搜索下一个可能的情况:如果符合要求,则表示寻找到一个正确答案. 在使用穷举法时,需要明确问题的答案的范围,这

  • 大数据情况下桶排序算法的运用与C++代码实现示例

    箱排序的变种.为了区别于上述的箱排序,姑且称它为桶排序(实际上箱排序和桶排序是同义词). 桶排序的思想是把[0,1)划分为n个大小相同的子区间,每一子区间是一个桶.然后将n个记录分配到各个桶中.因为关键字序列是均匀分布在[0,1)上的,所以一般不会有很多个记录落入同一个桶中.由于同一桶中的记录其关键字不尽相同,所以必须采用关键字比较的排序方法(通常用插入排序)对各个桶进行排序,然后依次将各非空桶中的记录连接(收集)起来即可. 注意: 这种排序思想基于以下假设:假设输入的n个关键字序列是随机分布在

  • C++实现矩阵原地转置算法

    C++实现矩阵原地转置算法

    本文实例描述了C++实现矩阵原地转置算法,是一个非常经典的算法,相信对于学习C++算法的朋友有很大的帮助.具体如下: 一.问题描述 微软面试题:将一个MxN的矩阵存储在一个一维数组中,编程实现矩阵的转置. 要求:空间复杂度为O(1) 二.思路分析 下面以一个4x2的矩阵A={1,2,3,4,5,6,7,8}进行分析,转置过程如下图: 图中右下角的红色数字表示在一维数组中的下标.矩阵的转置其实就是数组中元素的移动,具体的移动过程如下图: 我们发现,这些移动的元素的下标是一个个环,下标1的元素移动到

随机推荐