模板整理之线性同余方程组（逆元法）

2019-04-14 08:49发布

站内文章 / 模拟电子
10370 0 1590
#include #include #include #include #include using namespace std; int x,y,n,coe[100],remain[100],mod[100]; class X { public: int x,y; X(int a,int b) { x=a; y=b; return; } }; int ex_gcd(int num1,int num2) { if(!num2) { x=1; y=0; return num1; } int ans=ex_gcd(num1,num2); int tmp=x; x=y; y=tmp-(num1/num2)*x; return ans; } int get_inverse(int num,int m) { ex_gcd(num,m); return (x%m+m)%m; }//注:只有num和m互质时可以求逆元 X Liner_Cont_Equatoins() { int ans=0,M=1,cur_coe,cur_remain,cur_mod; for(int i=0;i<=n-1;i++) { cur_coe=coe[i];cur_remain=remain[i]-ans*coe[i];cur_mod=mod[i]; int d=ex_gcd(cur_coe,cur_mod); if(cur_remain%d) return X(-1,-1);//方程组无解 cur_coe/=d; cur_remain/=d; cur_mod/=d; int t; int inverse=get_inverse(cur_coe,cur_mod); t=(inverse*cur_remain)%cur_mod; t=(t+cur_mod)%cur_mod; ans+=M*t; M*=cur_mod; ans%=M; } return X(ans,M); } int main() { return 0; }

热门文章