C/C++教程

求逆元—穷举、扩展Euclid法

本文主要是介绍求逆元—穷举、扩展Euclid法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

方法1：穷举

#include<iostream>
using namespace std;
int main(){
    int m = 123,i;//求11mod123的逆元
    for (i = 2; (11*i-1)%123!=0; i++);
    cout << i;
    system("pause");
    return 0;
}

方法2：扩展Eulide

int Moni(int p,int q) {
    int s = 1, t = 0;
    int a = p, mod = q, tem;
    int z = mod / a;
    while (1 != a && 1 != mod) {
        tem = a;
        a = mod % a;
        mod = tem;
        tem = s;
        s =  t- s * z;
        t = tem;
        z = (int)mod / a;     
    }
    s = s % q;
    if (s < 0)
        s += mod;
    return s;
}

推荐文章 https://www.cnblogs.com/ZhouL3777/archive/2012/12/30/2839702.html

https://www.cnblogs.com/zishu/p/8650214.html

这篇关于求逆元—穷举、扩展Euclid法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航