線形同余方程式の解法ノート

#include<iostream>

#include<cstdio>

#include<vector>

using namespace std;



int gcd(int a,int b){

    return (b==0? a:gcd(b,a%b));

}



int exgcd(int a,int b,int &x,int &y)

{

    int d=a;

    if(b!=0){

        d=exgcd(b,a%b,y,x);

        y-=(a/b)*x;

    }else{

        x=1;y=0;

    }

    return d;

}



int mod_inverse(int a,int m)

{

    int x,y;

    exgcd(a,m,x,y);

    return (m+x%m)%m;

}



pair<int,int> linear_congruence(const vector<int>&A,const vector<int>&B,const vector<int>&M)

{

    int x=0,m=1;

    for(int i=0;i<A.size();i++){

        int a=A[i]*m,b=B[i]-A[i]*x,d=gcd(M[i],a);

        if(b%d!=0) return make_pair(0,-1);

        int t=b/d*mod_inverse(a/d,M[i]/d)%(M[i]/d);

        x=x+m*t;

        m*=M[i]/d;

    }

    return make_pair(x%m,m);

}

小さいノートをして、上のコードはすべてcopy<<挑戦プログラム設計コンテスト>という本で、以下は主に線形同余方程式のグループの解を求めるいくつかのノートです.
線形同余方程式群を解く考え方は,x=b 1(modm 1)(I)とax=b 2(modm 2)(II)を用いて新しいx'=b'(modm')のセットを解き,新しいグループでax=b 3(modm 3)を解き続けることである.
解の過程はまずx=b 1(mod m 1)を用いてx=b 1+m 1*t代入(II)と書くことができ,整理して得られる.
am 1*t=b 2-a*b 1(mod m 2)は、拡張ユークリッドを用いて知ることができ、この方程式には解当があり、d=gcd(am 1,m 2)|(b 2-a*b 1)のみであり、この条件を満たすと元の方程式は
(am 1/d)*t=((b 2-a*b 1)/d)mod(m 2/d)逆元の求め方(実質的に拡張ユークリッド)を用いて解くことができる
t=((b2-a*b1)/d)*mod_inverse(am1/d,m2/d) (mod m2/d)
すなわち、k値をt=k(mod m 2/d)、すなわちt=k+(m 2/d)*c(cは整数)として解く
x=b 1+m 1*tにx=b 1+m 1(k+(m 2/d)*c)がある.
x=b1+m1*k+m1*(m2/d)*c
したがって,新しい解のセットはx=b 1+m 1*k(mod m 1*(m 2/d))である.
この方法で反復すれば粗さが解ける~
解の方程式がそうである場合x=bi(mod ai)i=0,1,2,3...しかもai,ajの2つの互いに質を交換する時中国の残りの定理ですることができて、しかしあまり分かりません.--0
メモが終わる