精华内容
下载资源
问答
  • 大数乘法取模运算二进制
    千次阅读
    2018-10-02 09:58:04

    转载自 : https://www.cnblogs.com/geloutingyu/p/5886626.html

                    https://blog.csdn.net/snow_5288/article/details/71079692?utm_source=copy

     

    快速幂取模就是在O(logn)内求出a^n mod b的值。算法的原理是ab mod c=(a mod c)(b mod c)mod c 

    大数运算的实现方法主要有以下几种:

    1.  用字符串表示大数。将大数用十进制字符数组表示,然后按照“竖式计算”的思想进行计算。这种方法比较容易理解,但是计算效率比较低。
    2. 将大数看成二进制流进行处理。使用各种位运算和逻辑操作来实现打算的运算。该方法设计复杂,可读性较差,而且难以调试。
    3. 将大数表示成一个n进制数组。n的取值越大,数组的大小越小,这样可以缩短运算的时间及空间复杂度,提高算法的效率。在32位系统中,n可以取2^32,这时每一位的取值范围是0~0xffffffff。

     

    下面就针对第 (2)种方法进行描述与实现:

    在数据结构课关于栈的这一章中,我们都学过用“模2取余法”来将一个10进制数转换为一个二进制数,进而可以推广到“模n取余法”,经其转换为n进制(n任意指定)。

     

    问题:

    求 (a*b) % m 的值,其中 a,b,m 是1到10^18;

    如果直接乘的话,因为a和b还有m都很大,那么会溢出long long,所以需要一些方法;

    朴素的想法是用数组模拟高精度,但是比较麻烦;

    二进制数也是满足十进制竖式乘法运算规律的,我们可以模拟二进制乘法竖式来计算(a*b)%m,因为其每次只相当于a乘2,再取模就不会溢出了;

    #include <bits/stdc++.h>
    #define MAXN 100000+10
    #define ll long long
    using namespace std;
    
    ll multi(ll a, ll b, ll m)
    {
        ll ans=0;
        while(b)
        {
            if(b&1) (ans+=a)%=m;
            (a<<=1)%=m;
            b>>=1;
        }
        return ans;
    }
    
    int main(void)
    {
        std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
        ll a, b, m;
        cin >> a >> b >> m;
        cout << multi(a, b, m) << endl;
        return 0;
    }

     

    更多相关内容
  • 快速幂(二进制)取模运算

    千次阅读 2020-02-07 16:24:46
    在一些竞赛中,可能会遇到指数型的数据取模问题,这个时候直接用int或者long long 储存,就非常有可能超出计算机整数的存取范围(哈哈,一般都会超,毕竟是竞赛!!!),从而数据出错,所以我们就引出今...

    最近在牛客第一次碰到有关快速幂的知识,在此记录加深理解一下。大佬勿进,我怕《《 》》

    快速取幂的用途

    在一些竞赛中,可能会遇到指数型的数据取模问题,这个时候直接用int或者long long 储存,就非常有可能超出计算机整数的存取范围(哈哈,一般都会超,毕竟是竞赛!!!),从而数据出错,所以我们就引出今天的主角色 快速幂取模。这种方法在时间和空间都做了尽可能的优化,非常好用哦!

    快速幂取模的思路分析

    基本理论是离散数学的知识*(数学很重要!)*
    有一个引理我们需要清楚的:积的取余等于取余的积的取余。
    公式:(ab)%c = (a%c)(b%c)%c
    核心思想是将大数幂运算拆解成相应的乘法运算,利用上述式子,始终将我们的运算的数据量控制在c的范围下。

    以求a的b次方来介绍
    把b转换成二进制数。
    例如在这里插入图片描述
    11的二进制是1011
    在这里插入图片描述对二进制的位运算,在此就不赘述,有问题的同学请自行百度,这里我们需要用到“&”与“>>”运算符。

    先来一段具体代码,由代码来讲解

    ll binaryPow(ll num, ll k) 
    {
     ll ans = 1;
     while(k>0)
     {
      if(k&1)
       ans = ans*num%mod;//如果k的二进制位不是0,那么就会进行该步
      num = num*num%mod;//不断加倍
      k >>=1; //相当于每次除以2,用二进制看,不断的遍历k的二进制位
     }
     return ans;
    }

    在上面的代码中,k&1意思就是取k的二进制的最末位,11的二进制数为1011,第一次循环,取的是最右边的1,以此类推。k>>=1意思就是k右移一位,删去最低位置。
    接下来我来说说while循环中的原理。
    以num^11为例子,k = 11
    k 的二进制 1011。
    我们要理解num = num * num;这一步的作用。
    在这里插入图片描述哎嗨,快速幂就讲解完了。希望大家可以共同进步。另外注明一点,代码%mod也是为了防止溢出,这是从下面一道训练题想出来的。
    下面贴出来一道例题。
    题目链接
    https://ac.nowcoder.com/acm/contest/3003/G

    #include <cstdio>
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    using namespace std;
    typedef long long ll;
    const int maxn = 200005;
    const int mod = 1e9+10;
    typedef long long ll;
    ll binaryPow(ll num, ll k) 
    {
     ll ans = 1;
     while(k>0)
     {
      if(k&1)
       ans = ans*num%mod;
      num = num*num%mod;
      k >>=1; 
     }
     return ans;
    }
     
    int main()
    {
     ios::sync_with_stdio(false);
     int t;
     cin >> t;
     while (t--)
     {
      long long a, b, c, d, e, f, g;
      cin >> a >> b >> c >> d >> e >> f >> g;
      int sum = 0;
      int m = 1e9 + 7;
      if (binaryPow(a,d)+binaryPow(b,e)+binaryPow(c,f) == g)
      {
       cout << "Yes" << endl;
      }
      else
      {
       cout << "No" << endl;
      }
     }
     return 0;
    }

    就这样吧,溜走。

    展开全文
  • 基本的二进制算术运算算法,包括: 1. 总结2.减法3. 乘法4. 除法和取模5. 二进制-十进制转换 这些算法可用于计算非常大的整数,这是标准 Matlab 的变量类型无法处理的。 尽管可能不是最有效的,但这些对于教育目的和...
  • 快速幂二进制取模算法

    千次阅读 2016-07-23 10:57:46
    //实质上这步只是不断地使二进制位从右向左移动,实现的是使res乘的A值等于2^(对应位+1) 里面的乘号,是矩阵乘的运算,res是结果矩阵。 第3行代码每进行一次,二进制数就少了最后面的一个1。二进制数有多少个1就第3...

            矩阵的快速幂是用来高效地计算矩阵的高次方的。将朴素的o(n)的时间复杂度,降到log(n)。这里先对原理(主要运用了矩阵乘法的结合律)做下简单形象的介绍:一般一个矩阵的n次方,我们会通过连乘n-1次来得到它的n次幂。

            但做下简单的改进就能减少连乘的次数,方法如下:

           把n个矩阵进行两两分组,比如:A*A*A*A*A*A  =>  (A*A)*(A*A)*(A*A),这样就只需要计算一次A*A,然后将结果(A*A)连乘自己两次就能得到A^6,即(A*A)^3=A^6。算一下发现这次一共乘了3次,少于原来的3次。其实大家还可以取A^3作为一个基本单位。原理都一样:利用矩阵乘法的结合律,来减少重复计算的次数。

           以上都是取一个具体的数来作为最小单位的长度,这样做虽然能够改进效率,但缺陷也是很明显的,取个极限的例子(可能有点不恰当,但基本能说明问题),当n无穷大的时候,你现在所取的长度其实和1没什么区别。所以就需要我们找到一种与n增长速度”相适应“的”单位长度“,那这个长度到底怎么去取呢???这点是我们要思考的问题。

          有了以上的知识,我们现在再来看看,到底怎么迅速地求得矩阵的N次幂。

          既然要减少重复计算,那么就要充分利用现有的计算结果咯!~怎么充分利用计算结果呢???这里考虑二分的思想。大家首先要认识到这一点:任何一个整数N,都能用二进制来表示。。这点大家都应该知道,但其中的内涵真的很深很深(这点笔者感触很深,在文章的最后,我将谈谈我对的感想)!!

            计算机处理的是离散的信息,都是以0,1来作为信号的处理的。可想而知二进制在计算机上起着举足轻重的地位。它能将模拟信号转化成数字信号,将原来连续的实际模型,用一个离散的算法模型来解决。  好了,扯得有点多了,不过相信这写对下面的讲解还是有用的。

           回头看看矩阵的快速幂问题,我们是不是也能把它离散化呢?比如A^19  =>  (A^16)*(A^2)*(A^1),显然采取这样的方式计算时因子数将是log(n)级别的(原来的因子数是n),不仅这样,因子间也是存在某种联系的,比如A^4能通过(A^2)*(A^2)得到,A^8又能通过(A^4)*(A^4)得到,这点也充分利用了现有的结果作为有利条件。下面举个例子进行说明:

           现在要求A^156,而156(10)=10011100(2) ,也就有A^156=>(A^4)*(A^8)*(A^16)*(A^128)  考虑到因子间的联系,我们从二进制10011100中的最右端开始计算到最左端。细节就说到这,下面给核心代码:

    if(N&1)  
           res=res*A;     //二进制位为1时执行此步  
     n>>=1;  
     A=A*A;     //实质上这步只是不断地使二进制位从右向左移动,实现的是使res乘的A值等于2^(对应位+1)  

            里面的乘号,是矩阵乘的运算,res是结果矩阵。

          第3行代码每进行一次,二进制数就少了最后面的一个1。二进制数有多少个1就第3行代码就执行多少次。

          即每次执行第3行代码结果为:

    res* a^4 * a^8  *  a^16  *a^128 

          现在我就说下我对二进制的感想吧:

          我们在做很多”连续“的问题的时候都会用到二进制将他们离散简化

    Description

    Fermat's theorem states that for any prime number p and for any integer a > 1, ap = a (mod p). That is, if we raise a to the pth power and divide by p, the remainder is a. Some (but not very many) non-prime values of p, known as base-pseudoprimes, have this property for some a. (And some, known as Carmichael Numbers, are base-a pseudoprimes for all a.)

    Given 2 < p ≤ 1000000000 and 1 < a < p, determine whether or not p is a base-a pseudoprime.

    Input

    Input contains several test cases followed by a line containing "0 0". Each test case consists of a line containing p and a.

    Output

    For each test case, output "yes" if p is a base-a pseudoprime; otherwise output "no".

    Sample Input

    3 2
    10 3
    341 2
    341 3
    1105 2
    1105 3
    0 0
    

    Sample Output

    no
    no
    yes
    no
    yes
    yes
    #include<cstdio>
    #define N 45000
    struct st
    {
    	int a,b;
    }s[N];
    long quickpow(long n,long m,long mod)
    {
    	long ans=1,base=n;
    	
    	while(m)
    	{
    		if(m&1)
    		  ans=((ans%mod)*(base%mod))%mod;
    		base=((base%mod)*(base%mod))%mod;
    		m>>=1;				
    	}
    	return ans;
    }
    int main()
    {
    	int t,n,i,h;
    	long sum,m;
    	scanf("%d",&t);
    	while(t--)
    	{
    		sum=0;
    		scanf("%ld",&m);
    		scanf("%d",&h);
    		for(i=0;i<h;i++)
    		   scanf("%d%d",&s[i].a,&s[i].b);
    		for(i=0;i<h;i++)
    		   sum+=quickpow(s[i].a,s[i].b,m);
    		sum%=m;
    		printf("%ld\n",sum);
    	}
    	return 0;
    }

     

    (a+b+c+d+e)%x=(a%x+b%x+c%x+d%x+e%x)%x ;

     

    2、(a*b*c*d*e)%x=(a%x*b%x*c%x*d%x*e%x)%x ;

     

     

    展开全文
  • 整数部分,把十进制转成二进制一直分解至商数为0。读余数从下读到上,即是二进制的整数部分数字。 小数部分,则用其乘2,取其整数部分的结果,再用计算后的小数部分依此重复计算,算到小数部分全为0为止,之后读所有...

    十进数转成二进数

    整数部分采用 "除2取余,逆序排列"法。

    整数部分,把十进制转成二进制一直分解至商数为0。读余数从下读到上,即是二进制的整数部分数字。 小数部分,则用其乘2,取其整数部分的结果,再用计算后的小数部分依此重复计算,算到小数部分全为0为止,之后读所有计算后整数部分的数字,从上读到下。
    将59 转成二进制:

    整数部分:
    59 ÷ 2 = 29 ... 1
    29 ÷ 2 = 14 ... 1
    14 ÷ 2 =  7 ... 0
     7 ÷ 2 =  3 ... 1
     3 ÷ 2 =  1 ... 1
     1 ÷ 2 =  0 ... 1
    

    十进制的59转化二进制为111011

    二进位转成十进位

    方法:“按权展开求和”,该方法的具体步骤是先将二进制的数写成加权系数展开式,而后根据十进制的加法规则进行求和 [6] 。

    【例】:

    在这里插入图片描述

    规律:个位上的数字的次数是0,十位上的数字的次数是1,…,依次递增,而十分位的数字的次数是-1,百分位上数字的次数是-2,…,依次递减。

    二进制的1011对应十进制的11

    使用位运算(&)代替取模运算(%)

    符号描述运算规则
    &两个位都为1时,结果才为1
    |两个位都为0时,结果才为0
    ^异或两个位相同为0,相异为1
    ~取反0变1,1变0
    <<左移各二进位全部左移若干位,高位丢弃,低位补0
    >>右移各二进位全部右移若干位,对无符号数,高位补0,有符号数,各编译器处理方法不一样,有的补符号位(算术右移),有的补0(逻辑右移)

    位运算(&)效率要比取模运算(%)高很多,主要原因是位运算直接对内存数据进行操作,不需要转成十进制,因此处理速度非常快。

    a % b == a & (b - 1)
    

    前提:b 为 2^n

    来源自 HashMap 中的 indexFor 方法:

    static int indexFor(int h, int length) {
       return h & (length-1);//h%length
    }
    

    这个方法是使用哈希值对链表数组的长度取模,得到值所在的索引位置,里面使用位运算(&)代替普通的(%)运算。

    展开全文
  • 二进制运算

    2012-10-25 23:37:08
    java int 类型4个字节,1个字节有8位, int的类型有32位 32位的最高位上符号位,0表示正数,1表示负数 正数的原码,反码,补码都是一样 负数反码的原码的符号位不变,其它的位数取反(0-1==1-0) ...
  • 取模运算的理解和应用

    千次阅读 多人点赞 2020-07-01 10:11:10
    软件开发过程中,总会... 取模运算,在计算商值时,商值向负无穷方向舍入;尽可能让商值小的原则(不超多商值的最大值)。 例子: 取模 简述 商值 取模值 5 mod 3 = 2 5/3 = 1.66 商取小原则 商=1.
  • 大数取模二进制方法

    千次阅读 2018-09-30 16:18:23
    我们先把b转化为2进制 b=(a[t] a[t-1] a[t-2]....a[1] a[0]) (a[i]为0或1) 那么b = a[t]*2^t + a[t-1]*2^(t-1) + ... ... + a[1]*2^1 + a[0]*2^0(其中 a[i]=0,1) a^b mod c =a^(a[t]*2^t + a[t-1]*2^(t-1) + ...
  • 二进制补码运算

    千次阅读 多人点赞 2020-07-23 13:52:43
    二进制负数的在计算机中采用补码的方式表示。很多人很好奇为什么使用补码,直接使用原码表示多好,看上去更加直观和易于计算。然而事实告诉我们,这种直观只是我们人类的一厢情愿罢了,在计算机看来,补码才是它们最...
  • 快速幂取模即快速求出(a^b)mod c 的值。由于当a、b的值非常大时直接求a^b可能造成溢出,并且效率低。思路原理就是基于\(a*b...求解快速幂:设指数b用二进制表示为\(b = (b_n b_{n-1}...b_2b_1b_0)_2\),\(b = b_0 + ...
  • 二进制补码 加 减 取模 java代码实现

    千次阅读 2020-01-03 20:38:37
    ####实现二进制补码的加法 (全加法实现) 首先声明两个int类型的变量 CF 和OF,用来模拟加法过程中的进位和溢出 对于加法结果的每一位,都是由CF、oprend1、oprend2三位异或产生的结果(这三个数里面有奇数个1,...
  • Java%(取模运算)详解

    万次阅读 2017-01-20 10:58:46
    一.Java的取模运算1.实现算法public static double ramainder(double dividend, double dividor) { return dividend - dividend / dividor * dividor; }2.java的取模运算支持类型:字符型(自然不包括负数)、字节型...
  • 取模运算%和按位与&

    2020-04-01 21:35:57
    %:取模操作符是基于 十进制(人类思维) 的一种取模方式,如:11 % 4 = 3,常用在各种操作中,可判断奇偶,也可以用在哈希中,如:11 % 8 = 3,落在第 3 个槽中,即 $arr[3-1] 中 &:按位与是基于 二进制 的,如...
  • 区别主要表现在: 定点小数的小数点位置严格地设置在数的符号位与最高数值位之间,因此,数的表示范围和编码的取模值与用多少位二进制表示一个数无关,该位数只影响数值的精度。可以认为整数是小数点被设置在最低一位...
  • 大数运算包含加,减,乘,除,取模,幂运算,模幂运算。支持十进制运算二进制运算;支持文件运算,键盘输入运算,若有需要,可提供实验报告
  • 0. 整除与取模 xmody=x−y⋅⌊x/y⌋ 1. 应用 ...求一个数二进制形式 1 出现的次数: int bitCount(int n) { if (n == 0) { return 0; } return n % 2 + bitCount(n >> 1); // return ...
  • 程序源代码以及必要文件.rar
  • 那有没有一种专门为二进制数字提供的运算符呢?这就是本问题的主题:位运算符。先看看位运算符的定义:位运算符用来对二进制字节中的位进行位移或者测试处理,MySQL中提供的位运算符有按位或(|)、按位与(&)、按...
  • 文章目录前言一、模的概念二、10进制取模运算1.解释2.运算3.举例说明三、二进制计算机系统1.说明2. 取模与补码四、总结 前言 最近在看redis数据结构时,文中提到了全局哈希表,并且在redis Cluster(redis集群)...
  • 取模运算实例

    2021-11-25 21:04:21
     取模运算时,对于负数,应该加上被除数的整数倍,使结果大于或等于0之后,再进行运算.  也就是:(-1)%256 = (-1+256)%256=255%256=255   计算机存储角度:  计算机中负数是以补码形式存储的,-1的补码11111111,...
  • 快速幂&二进制&位运算

    千次阅读 2019-08-02 09:19:04
    好的标题就告诉我们该来的还是会来,学了十几年十进制现在告诉我要学二进制,但是这个东西很重要很重要,所以还是要重点记 part 1:什么是二进制二进制,是计算技术中广泛采用的一种数制,由德国数理哲学大师...
  • 取模运算的理解

    万次阅读 多人点赞 2019-07-17 16:42:19
    问题:在学习计算机组成中,不理解补码中取模运算的意义,故google一下,整理知识。 定义:模除(又称模数、取模操作、取模运算等,英语:modulo 有时也称作 modulus)得到的是一个数除以另一个数的余数。 公式:在...
  • matlab复数取模运算

    千次阅读 2021-04-18 04:18:37
    IFFT, 打乱相位可以采用函数F=F(randperm(numel(F))), 在打乱相位后进行反傅里叶变换时,新产生的序列会有虚数存在,这 里采取了取模值的方法进行下一步运算。...实验目的 1. 学会用 MATLAB 表示常用连续信号的方法; 2...
  • 学习背景:最近在看很多JAVA类的源码,遇到了很多的位运算,所以系统的学习了下有关二进制的知识。 首先,看一下JAVA中的基本数据的字节(Byte)长度和bit长度: 基本数据类型 字节Byte bit byte 1字节 8位 ...
  • python取模操作

    2020-11-29 04:50:44
    本文最先发布在:https:www.itcoder.techpostspython-modulo-operator 取模运算符是一个算术运算符,它计算一个数字除以另外一个数字之后,剩下的数字。 这个剩下的数字(余数)被称作模数。 例如,5除以3,等于1,...
  • Java算术运算符,取模

    2021-03-05 15:57:38
    又例如:a+b四则运算:加:+减:-乘:*除:/取模(取余数):%首先计算得到表达式的结果,然后再打印输出这个结果。复习一下小学一年级的除法公式:被除数/除数=商…余数对于一个整数的表达式来说,除法用的是整数,...
  • 3.3差错控制

    2019-12-02 10:07:25
    接收方收到的比特序列与生成多项式的二进制比特序列作模2除法,若结果余数为0,则没有出错,否则有错误。 进行如下的二进制模2除法,被除数为10110011010,除数为11001. 所得余数为0,因此二进制比特序列在...
  • poj 1995 快速幂二进制取模算法

    千次阅读 2015-08-24 16:35:16
    //实质上这步只是不断地使二进制位从右向左移动,实现的是使res乘的A值等于2^(对应位+1) } 里面的乘号,是矩阵乘的运算,res是结果矩阵。 第3行代码每进行一次,二进制数就少了最后面的一个1。二进制数有多少个1就...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 28,744
精华内容 11,497
关键字:

二进制取模运算