精华内容
下载资源
问答
  • 取模运算

    千次阅读 多人点赞 2018-08-07 20:55:09
    取模运算(“Modulo Operation”)和取余运算(“Complementation ”)两个概念有重叠的部分但又不完全一致。主要的区别在于对负整数进行除法运算时操作不同。取模主要是用于计算机术语中。取余则更多是数学概念。模...

    取模运算(“Modulo Operation”)和取余运算(“Complementation ”)两个概念有重叠的部分但又不完全一致。主要的区别在于对负整数进行除法运算时操作不同。取模主要是用于计算机术语中。取余则更多是数学概念。模运算在数论和程序设计中都有着广泛的应用比如:

    从奇偶数的判别

    素数的判别

    幂运算

    最大公约数的求法

    孙子问题

    凯撒密码问题

    虽然很多数论教材上对模运算都有一定的介绍,但多数都是以纯理论为主,对于模运算在程序设计中的应用涉及不多。

    为什么需要求余数呢?

    如果计算结果超出64位整数范围,就可能会输出结果对某个数取模后的结果。这样可以消除在高精度方面,由于语言的差异造成的不公和一些不利因素。例如,java里有支持高精度的类BIGINTEGER,python整数基本没有范围一说,而c系列就要靠自己实现。

    另一方面,高精度乘法不同实现的复杂度也不一样,对算法本身的评价更为困难。为了将重点放在对算法本身的评价上,竞赛中经常出现取余运算。

    我们不需要掌握太多相关运算规则,够用即可。

    1、n % p 得到结果的正负由被除数n决定,与p无关。例如:7%4 = 3, -7%4 = -3, 7%-4 = 3, -7%-4 = -3。

    2、大数取模可能比小数取模得出的结果更小,所以要输出最后结果可能是负数,我们可以这样输出:

    (A-B+MOD)%MOD,其中AB是取模以后的数。

    3、 (a + b) % p = (a % p + b % p) % p

    (a - b) % p = (a % p - b % p) % p

    (a * b) % p = (a % p * b % p) % p

    a ^ b % p = ((a % p)^b) % p

     

    贴几个大水问题code好了

    快速幂取模

    long long quick_mod(long long a, long long n, long long m)
    {
        long long ans = 1;
        while (n)
        {
            if (n & 1)
                ans = (ans * a) % m;
            n >>= 1;
            a = a * a % m;
        }
        return ans;
    }

    乘法取模

    long long mul_mod(long long a, long long b, long long m) // a * b % m
    {
        long long ret = 0;
        while (b)
        {
            if (b & 1)
                ret = (ret + a) % m;
            b >>= 1;
            a = (a << 1) % m;
        }
        return ret;
    }

     

    哦,最后提醒自己,以后遇见题直接上long long,再int自己扇自己

     

     

    展开全文
  • java和python在取模运算当除数与被除数都是正整数时的计算结果是一样的 5%3 值都是2 但是当存在负数的时候就有差别 java中: -5%3 得值 -2 它是这样计算得 -5/3 =-1.6666 n得值趋向于0,取-1 余数=-5-(-...

    java和python在取模运算当除数与被除数都是正整数时的计算结果是一样的

    5%3

    值都是2

     

    但是当存在负数的时候就有差别

    java中:

    -5%3    

    得值  -2 

    它是这样计算得  -5/3  =-1.6666     n得值趋向于0,取-1

    余数=-5-(-1*3)=-2     

     

     

    java中:

    -5%3    

    得值  1 

    它是这样计算得  -5/3  =-1.6666     n得值趋向于负无穷,取-2

    余数=-5-(-2*3)=1

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,012
精华内容 2,004
关键字:

取模运算