欢迎光临
我们一直在努力

C++数学-数论【费马小定理】流食般投喂

本编的学习要求:知道是什么,怎么用即可。

费马小定理:


【同余式】

  • 对于两个整数 a、b,模相同的模数 m,得到的余数相同,则称 a、b 模 m 同余,记作:。
  • a 和 b 模上 m 的余数相同,叫同余。

性质:

  • 同加性:两个整数加上相同的数,不影响结果,。
  • 同减性:如果同加性的 c 为负数,那么就出现了同减性,两个整数减去相同的数,也不影响结果。
  • 同乘性:两个整数乘上相同的数,不影响结果,。

📌这也是为什么之前的题目遇到 "乘加减" 运算时,可以处处取模的原因。

📌除法不能处处取模,本编就是通过 逆元,将除法转化乘 乘法,从而做到处处取模。


【费马小定理】

  • 如果 p 为质数,且 a、p 互质,则 a^(p – 1) % p = 1,官方记作:
  • 例如:p = 5,a = 2:2^(5 – 1) % 5 = 2^4 % 5 = 16 % 5 = 1,官方记作:

【乘法逆元】

  • 若 a 和 m 互质,且满足同余方程,则有,即 ax % m = 1,式子中 x 就是 a % m 的乘法逆元,记作:。
  • 例如:。

应用:

        即上文在同余式的红字:"📌除法不能处处取模,本编就是通过 逆元,将除法转化乘 乘法,从而做到处处取模。"

  • 现求 (b ÷ a)% p,等价于 (b * )% p,是 a % p 的乘法逆元,这个乘法逆元求解方法一:费马小定理 + 快速幂。
  • 费马小定理的作用:"a^(p – 1) % p = 1" 等价于 "a * a^(p – 2) % p = 1",对比 "ax % m = 1" 可知:乘法逆元等于 "a^(p – 2)"。
  • 快速幂的作用:计算 "a^(p – 2)"。
  • 乘法逆元求解方法一的使用条件是:p 为质数,a 与 p 互质;p 作为模数,题目一般给的都是质数,且很大,a 比 取模的模数 p 小,a 与 p 互质,所以条件一般符合。

    #include <iostream>

    using namespace std;

    typedef long long LL;

    // 必须要保证 a,p 互质,且 p 为质数。
    LL qpow(LL a, LL b, LL p)
    {
    LL ret = 1;
    while(b)
    {
    if(b & 1) ret = ret * a % p;
    b >>= 1;
    a = a * a % p;
    }
    return ret;
    }

    int main()
    {
    LL x, p; cin >> n >> p;
    cout << qpow(x, p – 2, p) << endl;
    return 0;
    }
    时间复杂度:

  • 与快速幂一致,为O(log n)。
赞(0)
未经允许不得转载:171主机测评 » C++数学-数论【费马小定理】流食般投喂
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址