精华内容
下载资源
问答
  • 形如 \(ax \equiv b \pmod n\) 式子称为线性方程。对于这样式子有解的充要条件是 \(gcd(a,n) \mid b\) . 于是扩展gcd求解 将原方程化为一次不定方程 \(ax+ny = b\) . 利用扩展欧几里得算法求解不定方程 $ ax...

    同余方程

    形如 \(ax \equiv b \pmod n\) 的式子称为线性同余方程。对于这样的式子有解的充要条件是 \(gcd(a,n) \mid b\) .

    于是扩展gcd求解
    将原方程化为一次不定方程 \(ax+ny = b\) .
    利用扩展欧几里得算法求解不定方程 $ ax + ny = b$ 的整数解的求解全过程,步骤如下:

    1、先计算 \(gcd(a,n)\),若 \(b\) 不能被 \(gcd(a,n)\) 整除,则方程无整数解;否则,在方程右边除以 \(b/gcd(a,n)\),记 得到新的不定方程 \(ax_0 + ny_0 = gcd(a,n)\).

    2、利用扩展欧几里德算法求出方程 $ax_0 + ny_0 = gcd(a, b) $的一组整数解 \(x_0\) , \(y_0\)

    3、根据数论中的相关定理,记 \(k=b/gcd(a,n)\),可得方程 \(ax + ny = b\) 的所有整数解为:

    \[ x = k*x_0 + n/gcd(a,n)* t \\ y =k* y_0 –a/gcd(a,n)* t \\ (t=0,1,2,……)\]
    调整得到关于 \(x\) 的正整数解
    注意因为解有多个,而我们要求最优解(正整数中最小的),所以 \((x+=n/gcd(a,n)\%(n/gcd(a,n))\);
    加法是为了保证正数,取模是为了最小

    青蛙的约会

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cstdlib>
    #include <cmath>
    using namespace std;
    long long  init(){
        long long  rv=0,fh=1;
        char c=getchar();
        while(c<'0'||c>'9'){
            if(c=='-') fh=-1;
            c=getchar();
        }
        while(c>='0'&&c<='9'){
            rv=(rv<<1)+(rv<<3)+c-'0';
            c=getchar();
        }
        return fh*rv;
    }
    long long x,y,m,n,l;
    long long exgcd(long long a,long long b,long long &x,long long &y){
        if(b==0){
            x=1;y=0;return a;
        }
        long long  t=exgcd(b,a%b,y,x);
        y-=(a/b)*x;
        return t;
    }
    int main(){
        freopen("in.txt","r",stdin);
        x=init();y=init();m=init();n=init();l=init();   
        if(m - n< 0) swap(m, n), swap(x, y);
        long long  a=0,b=0;
        long long  t=exgcd(m-n,l,a,b);
        if(n==m||(x-y)%t!=0){
            printf("Impossible");
            return 0;
        }
        (a*=(y-x)/t)%=(l/t);
        (a+=l)%=(l/t);//以保证最优解
        cout<<a;
        fclose(stdin);
        return 0;
    }
    

    exgcd可以用来求逆元

    \(ax \equiv 1 \pmod n\) 已知 \(a\) , \(n\)\(x\)
    因为 \(n\) 是个素数,所以 \(gcd(a,n)==1\) ;
    原方程可化为 \(ax \equiv gcd(a,n) \pmod n\)
    用exgcd求解即可。

    同余方程组

    \(x\%p_1 = b_1\)
    \(x\%p_2 = b_2\)
    \(x\%p_3 = b_3\)
    \(x\%p_4 = b_4\)
    \(x\) 的最小正整数解
    小范围数据直接枚举

    对于模数互质的情况,使用中国剩余定理(CRT)
    \(m=p_1p_2p_3 \ldots p_n\)
    构造出
    //定义 \(ni(k,p)\)\(k\) 在模 \(p\) 意义下逆元
    \[x = (m/p_1*ni(m/p_1, p_1)*a1 + \ldots) \% m\]
    CRT求解同余方程组

    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    using namespace std;
    long long a1,a2,a3,a4,b1,b2,b3,b4;
    long long m;
    long long exgcd(long long a,long long b,long long &x,long long &y){
        if(!b){
            x=1;y=0;
            return a;
        }
        long long t=exgcd(b,a%b,y,x);
        y-=a/b*x;
        return t;
    }
    long long ni(long long a,long long b){
        long long x=0,y=0;
        long long t=exgcd(a,b,x,y);
        if(t!=1) return -1;
        else return((x+b)%b);
    }
    int main(){
        freopen("in.txt","r",stdin);
        cin>>a1>>b1>>a2>>b2>>a3>>b3>>a4>>b4;
        m=a1*a2*a3*a4;
        cout<<(m/a1*ni(m/a1,a1)*b1+m/a2*ni(m/a2,a2)*b2+m/a3*ni(m/a3,a3)*b3+m/a4*ni(m/a4,a4)*b4)%m;
        fclose(stdin);
        return 0;
    }
    

    对于一般情况采用exgcd两两合并,
    \(x+a_1k_1=b_1\)
    \(x+k_2a_2=b_2\)
    \(a_1k_1-k_2a_2=b_1-b_2\)
    $t=exgcd(a_1,-a_2,k_1,k_2) $ 实际上 \(-a_2\) 可以写作 \(a_2\)
    合并:
    \(k_1=(k_1*(b_1-b_2)/t)\%a2\); //此处是模 \(a_2\) ,因为可以看成是模 \(a_2\)意义下的同余方程
    \(b_1-=a_1*k_1\) // \(b_1\) 就是原式中的 \(x\)
    \(a_1=a_1/t*a_2\) //把 $ a_1\(变成\)lcm(a1,a2)$
    \(b_1\%=a_1\) //把 \(b_1\) 调整至新式子的B
    此时就把两个式子合并为了一个,待所有的都合并完后,结果就是 \(b_1\) 调整好的最小正整数 \((b_1+=a_1)\%=a_1\)

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <cstdlib>
    #define LL long long 
    using namespace std;
    LL init(){
        LL rv=0,fh=1;
        char c=getchar();
        while(c<'0'||c>'9'){
            if(c=='-') fh=-1;
            c=getchar();
        }
        while(c>='0'&&c<='9'){
            rv=(rv<<1)+(rv<<3)+c-'0';
            c=getchar();
        }
        return rv*fh;
    }
    LL a,b,a1,b1;
    LL exgcd(LL a,LL b,LL &x,LL &y){
        if(!b){
            x=1;y=0;return a;
        }
        LL t=exgcd(b,a%b,y,x);
        y-=a/b*x;
        return t;
    }
    int main(){
        freopen("in.txt","r",stdin);
        a=init();b=init();
        for(int i=1;i<=3;i++){
            a1=init();b1=init();
            LL x=0,y=0;
            LL t=exgcd(a,a1,x,y);
            x=(x*(b-b1)/t)%a1;
            b-=a*x;
            a=a/t*a1;
            b%=a;
        }
        (b+=a)%=a;
        cout<<b;
        fclose(stdin);
        return 0;
    }

    求逆元

    \(ax \equiv 1 \pmod n\)
    逆元存在的充要条件是\(gcd(a,n)==1\);
    一般采用exgcd求逆元,若p是质数,也可使用费马小定理,快速幂
    模质数 \(P\) 意义下

    \(1! \sim n!\)

    先用快速幂处理出 \(n!^{-1}\),并预处理出来,\(1! \sim n!\),那么
    \[n^{-1} = n!^{-1} * (n - 1)!\]
    \[(n-1)!^{-1} = n!^{-1} * n\]
    由此递推即可

    从 $1 \sim n $

    此方法不需要求阶乘,代码简单
    首先 \(1^{-1} = 1\pmod p\)
    设 $p = k * i + r $, \(1 < i < p, r < i\)
    所以 \(k * i + r \equiv 0 \pmod p\)
    所有两边同乘以 \(i^{-1}*r^{-1}\)
    \[k * r^{-1} + i^{-1} \equiv 0 \pmod p\\ i^{-1} \equiv -k * r^{-1} \pmod p\\ i^{-1} \equiv -\lfloor p/r \rfloor * ( p\mod i)^{-1} \]

    N[i] = (p -p / i) * N[p % i] %p;

    转载于:https://www.cnblogs.com/Mr-WolframsMgcBox/p/7868283.html

    展开全文
  • 方程组 ...求关于 x 的同方程组 x%a1=b1 x%a2=b2 x%a3=b3 x%a4=b4 大于等于 0 最小整数。 【输入格式】 一行 8 个整数,表示a1,b1,a2,b2,a3,b3,a4,b4a1,b1,a2,b2,a3,b3,a4,b4 ...

    同余方程组

    mod.in/.out/.cpp

    【问题描述】

    求关于 x 的同余方程组

    x%=1

    x%=2

    x%=3

    x%=4

    的大于等于 0 的最小整数解。

    【输入格式】

    一行 8 个整数,表示,,,,,,,4  a1,b1,a2,b2,a3,b3,a4,b4 。

    【输出格式】

    一行一个整数,答案除以 p 的余数。

    【样例输入】

    2 0 3 1 5 0 7 3

    【样例输出】

    10

    【数据规模和约定】

    对于 30% 的数据,i  ai ≤ 40, 保证 i  ai 均为素数。

    对于 60% 的数据,110 3  1≤ai≤103 , 保证i  ai 均互素。

    对于 100% 的数据,0<,110 3  0≤bi<ai,1≤ai≤103 。

    【限制】

    时间:1S

    内存: 256M

    数据前六十膜数互素,可以用CRT求解

    不互素怎么办?用扩展欧几里得

    x%=1

    x%=2

    x%=3

    x%=4

    显然可以变成

    k1*a1+b1=x

    k2*a2+b2=x

    ....

    的形式

    那么 k1*a1+b1=k2*a2+b2移项 => a1*k1-a2*k2=b1-b2

    woc这不是ax+by=m么

    因为a,b并不互素,显然该式在(a,b)即(a1,a2)不整除m的时候是无解的

    此时可用扩展欧几里得求出一组特解x

    通解是

    X=x+k*lcm(a1,a2)

    由上式可知 X%lcm(a1,a2)=x,两个方程由此合并

    令 M=lcm(a1,a2) R=b2-b1

    合并后的方程为 X mod M = R

    那么合并n个方程就是按顺序来合并啦!即M=lcm(a1,a2,a3.....)

    那么上代码 其中数组m表示a,数组r表示b

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    #define LL long long
    LL a[6],r[6];
    int n;
    
    LL exgcd(LL a,LL b,LL &x,LL &y) {
        if(b==0) {x=1,y=0;return a;}
        LL tmp=exgcd(b,a%b,y,x);
        y-=a/b*x;
        return tmp;
    }
    LL solve() {
        LL M=a[1],R=r[1],x,y,d;
        for(int i=2;i<=4;i++) {
            d=exgcd(M,a[i],x,y);
            if((R-r[i])%d!=0) return -1;
            x=(R-r[i])/d*x%a[i];
            R-=x*M;
            M=M/d*a[i];
            R%=M;
        }
        return (R%M+M)%M;
    }
    
    int main() {
        for(int i=1; i<=4; i++)
        scanf("%lld%lld",&a[i],&r[i]);
        printf("%lld\n",solve());
        return 0;
    }

     

    转载于:https://www.cnblogs.com/sssy/p/7694035.html

    展开全文
  • 经历探索三元一次方程组的解法的过程;2.会三元一次方程组;3.能利用三元一次方程组解决简单的实际问题.电子课本__点击图片→查看大图▼▼▼知识点__三元一次方程组的一般步骤:①观察方程组中未知数的系数特点...

    d735678faf9a064c634a9a7efb36c5ec.png

    学习目标

    __

    1.经历探索三元一次方程组的解法的过程;

    2.会解三元一次方程组;

    3.能利用三元一次方程组解决简单的实际问题.

    电子课本

    __

    点击图片查看大图

    ▼▼▼

    ebfe40e2930ea1b9ea49f07492ed0a6a.png

    知识点

    __

    解三元一次方程组的一般步骤:

    ①观察方程组中未知数的系数特点,确定先消去哪个未知数;

    ②利用代入法或加减法,把方程组中的一个方程,与另外两个方程分别组成两组,消去同一个未知数,得到一个关于另外两个未知数的二元一次方程组;

    ③解这个二元一次方程组,求得两个未知数的值;

    ④将这两个未知数的值代入原方程组中较简单的一个方程中,求出第三个未知数的值,从而得到原三元一次方程组的解。

    微课精讲

    __

    图文解读

    __

    点击图片查看大图

    ▼▼▼

    4ddc2667acaa00d0c3d89e7d1c0facb8.png

    632c12bb8f78e6ca7311652c204d7252.png

    f54f031acb37c8fbfa34109862202ee6.png

    7c56c672f4568874b4f894be4a751b26.png

    f011347c9456126dd7aeb8afc5320a45.png

    622797139f647b8256e442a44b777c60.png

    3b43c839739ff428153cfc648137c0bc.png

    414a7bd843cc249cdf8f7fceecf45a13.png

    a79691d63a4791a966e549bd017470a5.png

    dec6245ed65487568b0728ff161a2897.png

    615efb7338b808d6ba6de35d9f106972.png

    3c708ff30ecd4f0912c0afde49b984e5.png

    同步练习

    __

    61cf52fe8d434a0c712c698157f531d9.png

    人教数学七年级下册微课目录

    第五章 相交线与平行线5.1《相交线》5.2《平行线及其判定》5.3《平行线的性质》5.4《平移》第六章 实数6.1《平方根》6.2《立方根》6.3《实数》第七章 平面直角坐标系7.1《平面直角坐标系》精讲7.2《坐标方法的简单应用》精讲第八章 平面直角坐标系8.1《二元一次方程组》精讲第九章 不等式与不等式组第十章 数据的收集、整理与描述

    免责声明:本文所有图文、音视频均来自网络,仅供学习交流使用,版权归原作者所有,除非无法确认,我们都会标明作者及出处,如有侵权烦请告知,我们会立即删除并表示歉意。谢谢! 

    ee722eaeb232e221e3480ccdcad0bc6d.png

    展开全文
  • 求关于 x 的同方程组 x%a1=b1a1=b1 x%a2=b2a2=b2 x%a3=b3a3=b3 x%a4=b4a4=b4 大于等于 0 最小整数。 【输入格式】 一行 8 个整数,表示a1,b1,a2,b2,a3,b3,a4,b4a1,b1,a2,b2,a3,b3,a4,b...

    【问题描述】

    求关于 x 的同余方程组

    x%=1  a1=b1

    x%=2  a2=b2

    x%=3  a3=b3

    x%=4  a4=b4

    的大于等于 0 的最小整数解。

    【输入格式】

    一行 8 个整数,表示,,,,,,,4  a1,b1,a2,b2,a3,b3,a4,b4 。

    【输出格式】

    一行一个整数,答案除以 p 的余数。

    【样例输入】

    2 0 3 1 5 0 7 3

    【样例输出】

    10

    【数据规模和约定】

    对于 30% 的数据,i  ai ≤ 40, 保证 i  ai 均为素数。

    对于 60% 的数据,110 3  1≤ai≤103 , 保证i  ai 均互素。

    对于 100% 的数据,0<,110 3  0≤bi<ai,1≤ai≤103 。

    【限制】

    时间:1S

    内存: 256M

     

    /**********************一般模线性方程组***********************/

    同样是求这个东西。。
    X mod m1=r1
    X mod m2=r2
    ...
    ...
    ...
    X mod mn=rn

    首先,我们看两个式子的情况
    X mod m1=r1……………………………………………………………(1)
    X mod m2=r2……………………………………………………………(2)
    则有 
    X=m1*k1+r1………………………………………………………………(*)
    X=m2*k2+r2
    那么 m1*k1+r1=m2*k2+r2
    整理,得
    m1*k1-m2*k2=r2-r1
    令(a,b,x,y,m)=(m1,m2,k1,k2,r2-r1),原式变成
    ax+by=m
    熟悉吧?

    此时,因为GCD(a,b)=1不一定成立,GCD(a,b) | m 也就不一定成立。所以应该先判 若 GCD(a,b) | m 不成立,则!!!方程无解!!!。
    否则,继续往下。

    解出(x,y),将k1=x反代回(*),得到X。
    于是X就是这两个方程的一个特解,通解就是 X'=X+k*LCM(m1,m2)
    这个式子再一变形,得 X' mod LCM(m1,m2)=X
    这个方程一出来,说明我们实现了(1)(2)两个方程的合并。
    令 M=LCM(m1,m2),R=r2-r1
    就可将合并后的方程记为 X mod M = R。

    然后,扩展到n个方程。
    用合并后的方程再来和其他的方程按这样的方式进行合并,最后就能只剩下一个方程 X mod M=R,其中 M=LCM(m1,m2,...,mn)。
    那么,X便是原模线性方程组的一个特解,通解为 X'=X+k*M。

    如果,要得到X的最小正整数解,就还是原来那个方法:

    X%=M;
    if (X<0) X+=M;

     

     1 #include<iostream>
     2 #include<cstdio>
     3 #include<cstring>
     4 #include<cmath>
     5 #include<algorithm>
     6 #include<queue>
     7 using namespace std;
     8 const int MAXN=100001;
     9 const int n=4;
    10 inline void read(int &n)
    11 {
    12     char c=getchar();bool flag=0;n=0;
    13     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
    14     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
    15 }
    16 int a[MAXN],b[MAXN];
    17 int exgcd(int a,int b,int &x,int &y)
    18 {
    19     if(b==0)
    20     {    x=1,y=0;return a;    }
    21     int r=exgcd(b,a%b,x,y);
    22     int tmp=x;x=y;y=tmp-(a/b)*y;
    23     return r;
    24 }
    25 int x,y;
    26 int gcd(int a,int b)
    27 {
    28     return b==0?a:gcd(b,a%b);
    29 }
    30 int lcm(int a,int b)
    31 {
    32     return a*b/(gcd(a,b));
    33 }
    34 inline int WORK()
    35 {
    36     /*
    37         x+a1*y1=b1   1
    38         x+a2*y2=b2   2
    39         x+a3*y3=b3   3
    40         求这个方程的解x 
    41     */
    42     int M=a[1],R=b[1],x,y;
    43     // M=LCM(a1,a2)
    44     // R=bi-b1
    45     for(int i=2;i<=n;i++)
    46     {
    47         
    48         /*
    49         a1*y1-a2*y2=b2-b1
    50         a*x  +b*y  =gcd(a,b)
    51         这样求出y1之后
    52         带回得到对于1,2两个方程的解x0=b1-y1*a1
    53         */
    54         int r=exgcd(M,a[i],x,y);
    55         if( (R-b[i])%r!=0)    return -1;
    56         /*   R-b[i]相当于b2-b1
    57              方程有解的条件(b2-b1)%gcd(a,b) ==0 */
    58         
    59         x=(R-b[i])/r*x%a[i];//**** 
    60         
    61         
    62         R=R-x*M;//x0=b1-y1*a1
    63         M=M/r*a[i];// 新的模数 
    64         R=R%M;//R=X mod M
    65     }
    66     return (R%M+M)%M;
    67 }
    68 int main()
    69 {
    70     
    71     for(int i=1;i<=n;i++)
    72         read(a[i]),read(b[i]);
    73     printf("%d",WORK());
    74     return 0;
    75 }

     

    转载于:https://www.cnblogs.com/zwfymqz/p/7692692.html

    展开全文
  • 1.自然语言描述 ...3.方程组的唯一为∑(i=1,k)aici(mod mi) 中国剩余定理有严格的条件限制,即模数之间两两互质。 一般的线性余方程组,将两个方程合并为一个,合并k-1次,最终得到一个线性余方程。 2
  • 线性方程组

    2018-02-02 09:32:00
    今天本蒟蒻只是想讲讲线性方程组的解法供各位大佬批评指错 我们现在有一些线性余方程 X=b1 (mod a1) X=b2 (mod a2) ... X=bn (mod an) 对于前面第一个方程,我们可以用exgcd求出一个X满足一式 不妨设X=a1*y1+...
  • 高次方程的解数及解法

    千次阅读 2013-08-10 19:14:15
    高次方程的解数及解法 分类: 数论2013-07-26 18:41 212人阅读 评论(0) 收藏 举报 定理一: 若是k个两两互质正整数,,则余式     (1) 与余式     ...
  • 但是如果不互质话,如果你要用中国剩余定理来解的话就显得没这么方便了,因为你在求那个类似逆元东西不好求,并且暴力求话时间也不允许 所以就需要一个更优秀东西来 解法 我们观察两个方程 x≡...
  • 二元一次方程组的解二元一次方程组的五种特殊解法1引入参数法解二元一次...方程组的五种特殊解法4同解重组法解二元一次方程组七年级——二元一次方程组的五种特殊解法5主元法解二元一次方程组七年级——用整体思想解...
  • 本文解决了用计算机算法解同方程组的问题
  • 线性方程组的一般形式: ,, 解线性方程组的方法; 消元法 克莱姆法则 逆矩阵法 当未知数非常大的时候,求逆是一件工作量非常大的事,所以一般采用消元法。 一、高斯消去法的基本思想 把方程组化成同解的...
  • 2016 Multi-University Training Contest 3 1004 HDU 5755 Gambler Bo ...高斯消元解同方程组,我做高斯消元第一个题,解法完全是参考别人,写博客就是存个板。#include #include #include #in
  • NOIP2012 方程的两种解法

    千次阅读 2012-11-19 14:34:58
    解法一:经典扩展欧几里得算法 ax+by=1,然后算出最小正整数 #include #include #include #include #include using namespace std; long long a,b,x,y; long long extended_gcd(long
  • 第一章 线性方程组解法 代数学起源于解方程(代数方程) 一元一次、一元二次、一元三次、一元四次都有求根公式(通过系数进行有限次加、减、乘、除、乘方、...1. 线性方程组的同解变形、线性组合、初等变换、...
  • 之前说过中国剩余定理传统解法的条件是m[i]两两互质,所以这题就不能用传统解法了= = 其实还有种方法: ...先来看只有两个式子的方程组: c≡b1 (mod a1) c≡b2 (mod a2) 变形得c=a1*x+b1,c=a2*x+...
  • 线性方程组即若干个线性...例如 以上适合笔算,但是在程序中表述一般解法,就需要用到等式合并或者中国剩余定理线性方程组解法与推理方法一,合并线性余方程以下为推导,红色圈出部分为编码时所用结论。...
  • 【线性方程组】 由若干个线性余方程构成线性...设自然数两两互质,并记,则方程组:在模 N 意义下,有唯一:。 2.证明 考虑方程组:, 由于两两互质,对方程组作变量替换,即令 故方程组等...
  • 高斯消去法 ... 例如,现有如下所示二元一次方程组。 将等式两边乘以一个实数,上下系数合并,消去其中一元未知数方法便是熟知加减法。 之后,把带入式1,得。 把上式用行列式表示如下
  • 一元线性方程组就是一堆形如 \(x \equiv a_1(mod \ \ m_1)\)的同余方程,然后一般让你求出一个最小正整数。 算法1 合并法 也就是我们将方程两两合并,然后求出合并后的解,从而推出最终。实现时候实际上...
  • 题目:求在小于等于N的正整数中有多少个X满足:X mod a[0] = b[0], X mod a...解法:先同上题一样用拓展欧几里德求出方程组的最后一个方程 X=ax+b,再调整 x 来求得 X 的的个数。一些解释请看下面的代码。 注...

空空如也

空空如也

1 2 3 4
收藏数 74
精华内容 29
关键字:

同解方程组的解法