首页 > 其他 > 详细

取模 分数取模 快速幂 费马小定理

时间:2020-05-31 23:48:48      阅读:62      评论:0      收藏:0      [点我收藏+]

INTRO

  • 有的题会让你对结果取模,有时候这个结果会是负数,有时候它会是分数,有时候 (a/b)mod p, b可能太大,会爆精度,所以要换为乘法。

负数取模

  • 因为有的编译器 % 是取模,有的是取余, 所以最好自己处理一下
  • 负数取模ex: -3 取模 4 == 1, -3 取余 4 == -3
  • 为了让编译器一定能取模, 则 \(a % MOD\) 写为 \((a+MOD)%MOD\)

分数取模 费马小定理 快速幂

什么是逆元

  • x是y的逆元, 则有 \(x*y \equiv 1\ mod\ P\)

什么是费马小定理

  • 前提:p是一个质数,a不是p的倍数
  • \(a^{p-1} \equiv 1\ mod\ p\)

什么是快速幂

  • 快速幂用来快速的求\((a^b)%m\)
  • 原理: 求\(a^b\), b可以写成二进制,然后将b分为多个\(2^k\)相加,则\(a^b\)可以分为多个\(a^{2^k}\)部份相乘。
  • 例如:求\(5^13\), 13可以写成\(1101\), 因此\(13=2^0+2^2+2^3\), 则\(a^13=a^{2^0+2^2+2^3} = a^{2^0}*a^{2^2}*a^{2^3}\), 其中 \(a^{2^{k+1}}\ =\ a^{2^k+2^k}\ =\ a^{2^k}*a^{2^k}\)
  • 代码
typedef long long ll;
ll binPow(ll a,ll b, ll m){
      ll ans = 0;
      while(b){
            if(b&1) ans = (ans*a)%m; //如果最低为是1
            a = (a*a) % m;
            b>>=1;
      }
      return ans;
}

怎么用快速幂、逆元求分数取模

  • 要求\((a/b)\ mod\ p\),把除换成乘,由于b有逆元c,即\((b*c)mod\ p\ \equiv 1 mod\ p\)
  • 则有 \((a/b)\ mod\ p \equiv ((a/b)*b*c)mod\ p\ \equiv (a*c)mod\ p\)
  • 那c是多少呢? 根据费马小定理,你可以知道 \(a^{p-1}\ mod\ p\ \equiv\ a*a^{p-2}\ mod\ p\)
  • 因此b的逆元\(c\equiv\ b^{p-2}\),其实就是\(b^{-1}\ mod\ p\equiv\ b^{p-1}\ mod\ p\)
  • 那怎么求c呢? 很多时候p都很大 例如1e9+7这样的,那我们就用快速幂求出b的逆元然后带回去就可以求到啦。

取模 分数取模 快速幂 费马小定理

原文:https://www.cnblogs.com/xuwanwei/p/13022199.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!