本文主要是介绍算法基础之线性同余方程，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
线性同余方程
-
核心思想：
-
转化为扩展欧几里得 求得结果d 必须为 b的因数
-
#include<iostream>#include<algorithm>using namespace std;typedef long long LL;const int N = 100010;int exgcd(int a,int b,int &x,int &y){if(!b){x = 1 ,y = 0;return a;}else{int d = exgcd(b, a % b , y , x);y -= a/b * x;return d;}}int main(){int n;cin>>n;while(n--){int a,b,m,x,y;scanf("%d %d %d", &a, &b, &m); //输入abm 其中am 为参数int d = exgcd(a,m,x,y);if(b % d) puts("impossible"); //如果b不是d的倍数 那么无解else cout<<(LL) x*b/d % m<<endl; //将x乘上系数 b/d 为了保证结果在int内要%m}}
-
这篇关于算法基础之线性同余方程的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
