精华内容
下载资源
问答
  • 同余式
    2020-09-19 18:41:41

    同余式

    1. 算法分析

    1.1 同余式常用定理

    1.1.1 欧拉公式/费马小定理

    欧拉公式:
        若gcd(a, n) = 1, 则aφ(n) = 1 (mod n)
    费马小定理
        若p是质数,则ap = a(mod p) => ap-1 = 1(mod p)
    欧拉公式/费马小定理常用来化简式子,通过aφ(n) = 1 (mod n)的关系,把式子的一部分转换为1

    1.1.2 威尔逊公式

    1. p为素数 <=> (p - 1)! ≡ -1(mod p)
    2. p为素数 <=> (p - 1)! ≡ (p - 1) (mod p)
    3. p为素数 <=> p | ((p-1)! + 1)

    因此,当发现算式有 (p-1)! 时,可以考虑威尔逊定理的使用

    1.1.3 扩展欧几里得

    对于方程:

    ax+by = m
    方程有解 <=> gcd(a, b) | m

    特殊地,ax+by=1有解 <=> gcd(a, b)=1
    输入a,b,使用扩展欧几里得算法可以求出ax + by = gcd(a, b)的一个解为(x0, y0),那么ax + by = gcd(a, b)的通解为:

    \begin{cases}
    x = x0+(b/gcd)*t \\
    y = y0-(a/gcd)*t 
    \end{cases}
    

    ax + by=m的通解为:

    \begin{cases}
    x = x0*m/gcd+(b/gcd)*t \\
    y = y0*m/gcd-(a/gcd)*t \\
    (这里的x0、y0是ax+by=gcd求出来的)
    \end{cases}
    

    ax+by=gcd(a, b)和ax+by=m的通解的周期都是b/gcd,不会变

    对ax+by=m进行变形,ax ≡ m (mod b)
    则x∈[0, b),解的数目为gcd(a, b)个,第一个解在[0, b/gcd),第二个解在[b/gcd, 2b/gcd),…

    1.2 乘法逆元

    1. 扩展欧几里得
      ax ≡ 1(mod p) <=> ax + py ≡ 1(mod p),因此可以使用扩展欧几里得求ax + py ≡ 1(mod p)解逆元,求出来的逆元就是x

    2. 费马小定理
      ap-1 ≡ 1(mod p) <=> a的逆元为ap-2(mod p),当且仅当p为素数情况

    3. 线性求逆元
      首先有
      1-1≡1(mod p)

      p=k * i + r, r < i, 1 < i < p
      两边同时mod p,有
      k * i + r ≡0 (mod p)
      两边同时乘上i-1 * r-1,得到
      k* r-1+ i-1≡ 0(mod p)
      移项
      i-1≡-k * r-1 (mod p)
      i-1≡-⌊P/i⌋ * (p mod i)-1 (mod p)
      以inv(i)表示i在mod p下的逆元,则有递推公式:
      inv[i]= -(p/i) * inv[p % i]

    1.3 求解同余式

    1.3.1 求解一次同余式

    求解一次同余式 ax ≡ 1(mod p), 直接乘法逆元求解

    1.3.2 求解高次同余式

    求解高次同余式 ax ≡ 1(mod p), 使用baby Step,Giant Step算法求解

    1.4 中国剩余定理

    1. 原始版中国剩余定理

    假设整数m1,m2, … ,mn两两互质,则对任意的整数:a1,a2, … ,an,方程组 (S) 有解,并且通解可以用如下方式构造得到:

    \begin{cases}
    x ≡ a1 (mod m1) \\
    x ≡ a2 (mod m2) \\ 
    x ≡ a3 (mod m3) \\
    x ≡ a4 (mod m4)
    \end{cases}
    

    有解的判定条件,并用构造法给出了在有解情况下解的具体形式。
    中国剩余定理说明:假设整数m1,m2, … ,mn两两互质,则对任意的整数:a1,a2, … ,an,方程组 有解,并且通解可以用如下方式构造得到:
    x = ∑ i = 1 n   a i ∗ t i ∗ M i + k M x = \sum_{i=1}^n\ {ai * ti * Mi} + kM x=i=1n aitiMi+kM
    在mod M的意义下:
    x = ( ∑ i = 1 n   a i ∗ t i ∗ M i ) m o d M x = (\sum_{i=1}^n\ {ai * ti * Mi} ) mod M x=(i=1n aitiMi)modM

    1. 拓展版中国剩余定理

    普通的中国剩余定理要求所有的mi互素, 那么如果不互素呢,求解同余方程组方法如下:
    ①这种情况采用两两合并的思想,假设要合并如下两个方程:
    x = a1 + m1x2
    x = a2 + m2x2
    那么得到: a1+ m1x1 = a2 + m2x2 => m1x1 + m2x2 = a2 - a1

    ②使用扩展欧几里得算法得到一个最小的x1,从而得出最小的x使他满足:
    x = a1 + m1x1 = a2 + m2x2
    这样得到的是x的一个特解x’,当然也是最小正整数解

    ③所以x的通解一定是x’加上lcm(m1,m2)*k,这样才能保证x模m1和m2的余数是a1和a2.由此,我们把这个x’当作新方程的余数,把lcm(m1, m2)当作新的方程的模数
    合并完成:x ≡ x’ (mod lcm(m1, m2))

    1.5 思维同余性质

    • 同余的考题很多结合距离可以回头的概念,比如自西向东一旦到了尽头那么又是自西向东,这样会产生同余的情况
    • 还有很多考察欧拉公式等

    2.板子

    2.1 同余式常用定理

    扩展欧几里得算法

    // 扩展欧几里得算法:ax+by=gcd(a, b),返回值为d=gcd(a, b)
    int exgcd(int a, int b, int &x, int &y) {
        if (!b) {   // b==0时,x=1, y=0
            x = 1, y = 0;
            return a;
        }
        int d = exgcd(b, a % b, y, x); // b != 0时,gcd(a, b) = gcd(b, a % b), x = x, y = y - a/b * x;
        y -= a / b * x;
        return d;
    }
    

    2.2 乘法逆元

    1. 扩展欧几里得求逆元
    // 扩展欧几里得算法:ax+by=gcd(a, b),返回值为d=gcd(a, b)
    LL exgcd(LL a, LL b, LL &x, LL &y) {
        if (!b) {  // b==0时,x=1, y=0
            x = 1, y = 0;
            return a;
        }
        LL d = exgcd(b, a % b, y, x); // b != 0时,gcd(a, b) = gcd(b, a % b), x = x, y = y - a/b * x;
        y -= a / b * x;
        return d;
    }
    
    LL getInv(LL a, LL mod) {  //求a在mod下的逆元,不存在逆元返回-1
        LL x, y;
        LL d = exgcd(a, mod, x, y);
        return d == 1 ? (x % mod + mod) % mod: -1;
    }
    
    1. 费马小定理求逆元
    LL qmi(LL a, LL k, LL p)   {
        LL res = 1 % p;  // res记录答案, 模上p是为了防止k为0,p为1的特殊情况
        while(k) { // 只要还有剩下位数
            if (k & 1) res = (LL)res * a % p;  // 判断最后一位是否为1,如果为1就乘上a,模上p, 乘法时可能爆int,所以变成long long
            k >>= 1;  // 右移一位
            a = (LL) a * a % p;  // 当前a等于上一次的a平方,取模,平方时可能爆int,所以变成long long
        }
        return res;
    }
    
    LL get_inv(LL a, LL p) {
        return qmi(a, p - 2, p);
    }
    
    1. 线性求逆元

    打表

    / inv[i]=-(mod/i)*inv[i%mod]
    LL inv[mod+5];
    void getInv(LL mod) {
        inv[1]=1;
        for(int i=2;i<mod;i++)
            inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    }
    

    递归

    LL inv(LL i) {
        if(i==1)return 1;
        return (mod-mod/i)*inv(mod%i)%mod;
    }
    

    2.3 求解同余式

    1. 求解一次同余式
      直接逆元,见2.2

    2. 求解高次同余式

    // 求解a^x=b(mod p),返回值为x
    int baby_step_giant_step(int a, int b, int p) {
        map<int, int> hash; 
        hash.clear();
        b %= p;
        int t = (int)sqrt(p) + 1;
        for (int j = 0; j < t; ++j) {
            int val = (LL)b * qmi(a, j, p) % p;
            hash[val] = j;
        }
        a = qmi(a, t, p);
        if (a == 0) return b == 0? 1: -1;
        for (int i = 0; i <= t; ++i) {
            int val = qmi(a, i, p);
            int j = hash.find(val) == hash.end()? -1: hash[val];
            if (j >= 0 && i * t - j >= 0) return i * t - j;
        }
        return -1;
    }}
    

    2.4 中国剩余定理

    1. 原始版中国剩余定理–模数互质
    // 扩展欧几里得算法:ax+by=gcd(a, b),返回值为d=gcd(a, b)
    int exgcd(int a, int b, int &x, int &y) {
        if (!b) {  // b==0时,x=1, y=0
            x = 1, y = 0;
            return a;
        }
        int d = exgcd(b, a % b, y, x); // b != 0时,gcd(a, b) = gcd(b, a % b), x = x, y = y - a/b * x;
        y -= a / b * x;
        return d;
    }
    
    
    //a, m --- 第i个方程表示x ≡ ai(mod mi)
    // n---- 方程个数
    int CRT( int a[], int m[], int n ) {  //x ≡ ai(mod mi)
        int M = 1;
        for(int i=0;i<n;++i) M *= m[i];
        int ret = 0;
        for(int i=0;i<n;++i) {
            int x,y;
            int tm = M/m[i];
            exgcd(tm,m[i],x,y);//调用外部函数:拓展欧几里得
            ret = (ret+tm*x*a[i])%M;
        }
        return (ret+M)%M;
    }
    
    1. 扩展版中国剩余定理–模数不互质
    // 扩展欧几里得算法
    LL exgcd(LL a, LL b, LL &x, LL &y) {
        if (!b) {
            x = 1, y = 0;
            return a;
        }
        int d = exgcd(b, a % b, y, x);
        y -= a / b * x;
        return d;
    }
    
    int main() {
        int n;
        cin >> n;
        bool ans = true;  // 判断是否有答案
        LL a1, m1;
        cin >> a1 >> m1;  // x≡mi(mod ai)
        for (int i = 0; i < n - 1; ++i) {
            LL a2, m2;
            scanf("%lld %lld", &a2, &m2);
            LL k1 ,k2;
            LL d = exgcd(a1, a2, k1, k2);  // 扩张欧几里得算法得到k1,k2,d
            if ((m2 - m1) % d) {  // 如果能够整除,裴属等式无解,则题目无解
                ans = false;
                break;
            }
            k1 = k1 * (m2 - m1) / d;  // 计算k1的实际值(扩张欧几里得算出的是ax+by=gcd(a, b)情况下的k1)
            LL t = a2 / d;  // 得到k①=k1+k*a2/d中的斜率a2/d
            k1 = (k1 % t + t) % t;  // 取得正整数范围内的最小的k1
            m1 = k1 * a1 + m1;  // 得到x通解x=ka+m1
            a1 = abs(a1 * a2 / d);  // 得到通解形式下的斜率a
        }
        if (ans) {
            cout << (m1 % a1 + a1) % a1 << endl;  // 有解输出满足x≡mi(mod ai)的最小x
        }
        else cout << -1 << endl;  // 无解输出-1
        return 0;
    }
    

    3. 例题

    3.1 同余式常用定理

    hdu2973-YAPTCHA
    题意: 计算$ s_n = \sum_{k=1}^n[\frac{(3k + 6)! + 1}{3k + 7} - [\frac{(3k+6)!}{3k+7} ] ]$
    给定1e6个测试样例,每个测试样例给一个n~1e6,求sn
    题解:
    题目的意思就是求题目中的Sn式子的值,出现(p-1)!的形式,考虑威尔逊定理
    其中[x]表示不大于x的最大整数。
    威尔逊定理:当且仅当p为素数时,( p − 1)!≡−1(mod p)。
    分析:如果3k+7为质数,根据定理,那么[((3k+6)! + 1)/(3k+7) - [(3k+6)!/(3k+7)]]相减就为1,否则这两个数差为0。
    令p=3*k+7
    1.若p是素数, ( (p-1)!+1 )/p是个整数,设为x,则(p-1)!/p比这个整数小一点点,取整后是x-1,
    则[ ( (p-1)!+1 )/p - [(p-1)!/p] ]=1;
    2.若p是合数,(p-1)!/p是个整数,设为y,则( (p-1)!+1 )/p比这个整数大一点点,取整后还是y,
    则[ ( (p-1)!+1 )/p - [(p-1)!/p] ]=0;
    代码:

    
    #include <iostream>
    
    using namespace std;
    
    int const N = 1e6;
    int prime[N * 3 + 7], st[N * 3 + 7], s[N * 3 + 7];
    
    // 利用线性筛法来得到素数表
    void get_prime(int n) {
        int cnt = 0;
        for (int i = 2; i <= n * 3 + 7; ++i) {
            if (!st[i])
                prime[cnt++] = i;
            for (int j = 0; prime[j] <= (n * 3 + 7) / i; ++j) {
                st[prime[j] * i] = true;
                if (i % prime[j] == 0) break;      
            }                
        }
        for (int i = 2; i <= n; ++i) {  // 前缀和s[i]记录到值为i时有多少个素数
            if (!st[3 * i + 7]) s[i] = s[i - 1] + 1;
            else s[i] = s[i - 1];
        }
    }
    
    int main() {
        int T;  // 输入样例数目
        cin >> T;   
        get_prime(N);  // 利用线性筛素数打印素数表
        while(T--) {
            int n;  // 读入数组
            cin >> n;
            printf("%d\n", s[n]);  // 打印对应的素数个数
        }
        
        return 0;
    }
    

    3.2 求解同余式

    acwing203同余方程
    题意: 求关于x的同余方程 ax ≡ 1(mod b) 的最小正整数解。
    题解: 注意b不一定是素数
    代码:

    #include <bits/stdc++.h>
    
    using namespace std;
    
    typedef long long LL;
    
    int a, b;
    
    LL exgcd(LL a, LL b, LL &x, LL &y) {
        if (!b) {
            x = 1, y = 0;
            return a;
        }
        LL d = exgcd(b, a % b, y, x); // b != 0时,gcd(a, b) = gcd(b, a % b), x = x, y = y - a/b * x;
        y -= a / b * x;
        return d;
    }
    
    LL getInv(LL a,LL mod) {
        LL x, y;
        LL d = exgcd(a, mod, x, y);
        return d == 1 ? (x % mod + mod) % mod: -1;
    }
    
    int main() {
        cin >> a >> b;
        cout << getInv(a, b);
        return 0;
    }
    

    acwing224计算器
    题意: 计算快速幂、一次线性同余、高次同余方程
    题解: 模板
    代码:

    #include <bits/stdc++.h>
    
    using namespace std;
    
    typedef long long LL;
    int t, type, y, z, p;
    
    LL qmi(LL a, LL k, LL p) {
        LL res = 1 % p;
        while (k) {
            if (k & 1) res = res * a % p;
            k >>= 1;
            a = a * a % p;
        }
        return res;
    }
    
    // 扩展欧几里得算法:ax+by=gcd(a, b),返回值为d=gcd(a, b)
    LL exgcd(LL a, LL b, LL &x, LL &y) {
        if (!b) {
            x = 1, y = 0;
            return a;
        }
        LL d = exgcd(b, a % b, y, x); // b != 0时,gcd(a, b) = gcd(b, a % b), x = x, y = y - a/b * x;
        y -= a / b * x;
        return d;
    }
    
    LL getInv(LL a,LL mod) {
        LL x, y;
        LL d = exgcd(a, mod, x, y);
        return d == 1 ? (x % mod + mod) % mod: -1;
    }
    
    int baby_step_giant_step(int a, int b, int p) {
        map<int, int> hash; 
        hash.clear();
        b %= p;
        int t = (int)sqrt(p) + 1;
        for (int j = 0; j < t; ++j) {
            int val = (LL)b * qmi(a, j, p) % p;
            hash[val] = j;
        }
        a = qmi(a, t, p);
        if (a == 0) return b == 0? 1: -1;
        for (int i = 0; i <= t; ++i) {
            int val = qmi(a, i, p);
            int j = hash.find(val) == hash.end()? -1: hash[val];
            if (j >= 0 && i * t - j >= 0) return i * t - j;
        }
        return -1;
    }
    
    int main() {
        cin >> t >> type;
        while (t--) {
            cin >> y >> z >> p;
            if (type == 1) {
                cout << qmi(y, z, p) << endl;
            }
            else if (type == 2) {
                LL res = getInv(y, p);
                if (res == -1) {
                    cout << "Orz, I cannot find x!\n";
                    continue;
                }
                else cout << (z * res % p + p ) % p << endl;
            }
            else{
                LL res = baby_step_giant_step(y, z, p);
                if (res == -1) {
                    cout << "Orz, I cannot find x!\n";
                    continue;
                }
                else cout << res << endl;
            }
        }
        return 0;
    }
    

    acwing202最幸运的数字

    3.3 中国剩余定理

    acwing1298曹冲养猪
    题意: 有X头猪,当建立ai个猪圈,有bi头猪没有去处。输入n个条件,每个条件为ai,bi,求出X。n~10, ai、bi~1e6, ai*bi <= 1e18
    题解: crt模板
    代码:

    #include<bits/stdc++.h>
     
    using namespace std;
    
    typedef long long LL;
    
    // 扩展欧几里得算法:ax+by=gcd(a, b),返回值为d=gcd(a, b)
    LL exgcd(LL a, LL b, LL &x, LL &y) {
        if (!b) {
            x = 1, y = 0;
            return a;
        }
        LL d = exgcd(b, a % b, y, x); // b != 0时,gcd(a, b) = gcd(b, a % b), x = x, y = y - a/b * x;
        y -= a / b * x;
        return d;
    }
    
    //a, m --- 第i个方程表示x ≡ ai(mod mi)
    // n---- 方程个数 
    LL CRT( LL a[], LL m[], LL n ) {
        LL M = 1;
        for(LL i=0;i<n;++i) M *= m[i];
        LL ret = 0;
        for(LL i=0;i<n;++i) {
            LL x,y;
            LL tm = M/m[i];
            exgcd(tm,m[i],x,y);//调用外部函数:拓展欧几里得
            ret = (ret+tm*x*a[i])%M;
        }
        return (ret+M)%M;
    }
     
    int main() {
        int n;
        cin >> n;
        LL a[11], m[11];
        for (int i = 0; i < n; ++i) {
            cin >> m[i] >> a[i];
        }
        cout << CRT(a, m, n) << endl;
        return 0;
    }
    

    acwing204表达整数的奇怪方式
    题意: 给定 2n 个整数a1,a2,…,an和m1,m2,…,mn,求一个最小的非负整数 x,满足∀i∈[1,n],x≡mi(mod ai)。
    题解:
    对应任意的a1,m1,a2,m2
    如果x≡m1(mod a1), x≡m2(mod a2)
    则x = k1a1+m1, x = k2a2+m2
    则有k1a1+m1=k2a2+m2,则有k1a1-k2a2=m2-m1,这个二元一次方程的解集为k①=k1+k * a2/d,k②=k2+k * a1/d
    把解集带入第三行,有x = ka1a2/d+k1a1+m1=ka+m1 (其中m1 = k1a1+m1, a = a2 * a1 / d)
    因此,求解本题时,可以先借助扩展欧几里得算法求出k1和k2
    从而计算出最小的k①,得到x的通解x=ka+m1,取最小的即可
    本题求满足x≡7(mod 8), x≡9(mod 11)的最小x
    代码:

    #include <bits/stdc++.h>
    
    using namespace std;
    
    typedef long long LL;
    
    // 扩展欧几里得算法
    LL exgcd(LL a, LL b, LL &x, LL &y) {
        if (!b) {
            x = 1, y = 0;
            return a;
        }
        int d = exgcd(b, a % b, y, x);
        y -= a / b * x;
        return d;
    }
    
    int main() {
        int n;
        cin >> n;
        bool ans = true;  // 判断是否有答案
        LL a1, m1;
        cin >> a1 >> m1;  // x≡mi(mod ai)
        for (int i = 0; i < n - 1; ++i) {
            LL a2, m2;
            scanf("%lld %lld", &a2, &m2);
            LL k1 ,k2;
            LL d = exgcd(a1, a2, k1, k2);  // 扩张欧几里得算法得到k1,k2,d
            if ((m2 - m1) % d) {
                ans = false;
                break;
            }
            k1 = k1 * (m2 - m1) / d;  // 计算k1的实际值(扩张欧几里得算出的是ax+by=gcd(a, b)情况下的k1)
            LL t = a2 / d;  // 得到k①=k1+k*a2/d中的斜率a2/d
            k1 = (k1 % t + t) % t;  // 取得正整数范围内的最小的k1
            m1 = k1 * a1 + m1;  // 得到x通解x=ka+m1
            a1 = abs(a1 * a2 / d);  // 得到通解形式下的斜率a
        }
        if (ans) {
            cout << (m1 % a1 + a1) % a1 << endl;
        }
        else cout << -1 << endl;  // 无解输出-1
        return 0;
    }
    

    3.4 思维同余性质

    acwing222青蛙的约会
    题意: 两只青蛙,初始位置分别在x,y。两只青蛙每次跳的距离分别为m, n,路是一个环(跳到头再往前跳相当于从开始跳),总长为l,求要使两只青蛙能够相遇,最少两只青蛙都需要跳几次。x,y,m,n,l~2e9
    题解: 设初始位置分别为a,b,每次两只青蛙跳的步数为m和n,因此两只青蛙能够遇到就要满足:
    (m - n) * x - y * l = b - a
    所以就是要去寻找式子中的x,然后考虑使用扩展欧几里得求参数即可
    同时要注意,求出来的x可能是负数,因此需要去寻找该剩余内其他的最小的正数
    而x的通解形式为:x=x0 * m/gcd+k * (b/d),通过这个方式求得正整数解
    代码:

    #include<bits/stdc++.h>
     
    using namespace std;
    
    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 d = exgcd(b, a % b, y, x);
        y -= a / b * x;
        return d;
    }
     
    int main() {
        long long x, y, m, n, l, a, b;
        cin >> a >> b >> m >> n >> l;
        long long d = exgcd(m - n, l, x, y);
        if ((b - a) % d) printf("Impossible\n");
        else  {
            x *= (b - a) /d ;
            long long t = abs(l / d);
            cout << (x % t + t) % t << endl;
        }
        return 0;
    }
    
    
    更多相关内容
  • 一次同余式求解和相关理论

    千次阅读 2019-03-15 19:58:43
    同余式的定义&;一次同余式求解的通用方法.

    定义

    形如 f ( x ) ≡ 0 ( m o d m ) f(x)\equiv 0\pmod m f(x)0(modm)的方程称同余式. f ( x ) f(x) f(x)是整数系数多项式. f ( x ) f(x) f(x)是形如 a x + b ax+b ax+b的是一次同余式.

    明显的,一个有解的同余式解是无限的,但是都在若干个对m的剩余系内.所以称满足条件的剩余系的个数为解数.
    下面以解一个一次同余式的过程解释一次同余式的解法和相关性质.


    例程

    6 x ≡ 28 ( m o d 32 ) 6x \equiv 28\pmod{32} 6x28(mod32)

    判断有无解

    T h e o r e m : 同 余 式 a x ≡ b ( m o d m ) 有 解 的 充 要 条 件 是 ( a , m ) ∣ b . 在 有 解 的 情 况 下 , 解 数 为 g c d ( a , m ) . {Theorem:}\\ 同余式 ax\equiv b \pmod m有解的充要条件是( a,m )| b.\\在有解的情 况下,解数为gcd(a,m). Theorem:axb(modm)(a,m)b.gcd(a,m).
    解释:
    ax=km+b, ax-km=b,要有整数解x,k,则根据裴蜀定理,有且仅有sa+tb=gcd(a,b)*k有整数解.
    AArmCQ.png
    实际上就是裴蜀定理中用表格求解的那个gcd(a,b)=sa+tb.

    该式gcd(6,32)=2|28,有解.并根据性质(互质两个同除,不互质三个同除)约简为
    3 x ≡ 14 ( m o d 1 ) 6 3x\equiv 14\pmod 16 3x14(mod1)6

    通解和解数

    T h e o r e m : 如 果 有 解 , 且 求 出 特 解 x 0 , 那 么 通 解 为 x ≡ x 0 + t ⋅ m g c d ( a , m ) ( m o d m ) . {Theorem:}\\ 如果有解,且求出特解x_0,那么通解为x\equiv x_0+t\cdot \frac{m}{gcd(a,m)}\pmod m. Theorem:,x0,xx0+tgcd(a,m)m(modm).
    解释:
    由二元一次不定方程的平衡理论,当不定方程 b = a x + k m b=ax+km b=ax+km有特解 x 0 , k 0 x_0,k_0 x0,k0时,步进 △ p \triangle p p应为 [ a , m ] = a , m g c d ( a , m ) [a,m]=\frac{a,m}{gcd(a,m)} [a,m]=gcd(a,m)a,m此时 △ x = p / a , △ k = p / m . \triangle x=p/a,\triangle k=p/m. x=p/a,k=p/m.
    所以 △ x \triangle x x应为步进的整数倍.即 x ≡ x 0 + t ⋅ m g c d ( a , m ) ( m o d m ) x\equiv x_0+t\cdot \frac{m}{gcd(a,m)}\pmod m xx0+tgcd(a,m)m(modm).
    另外,由于余数应取mod m,即 x 0 + t ⋅ m g c d ( a , m ) &lt; m x_0+t\cdot \frac{m}{gcd(a,m)}&lt;m x0+tgcd(a,m)m<m
    即要完成一个大小为m周期,步进数为gcd(a,m).所以解数为 g c d ( a , m ) gcd(a,m) gcd(a,m).
    还有一种说法是对于解 x 0 + t ⋅ m g c d ( a , m ) x_0+t\cdot \frac{m}{gcd(a,m)} x0+tgcd(a,m)m在gcd(a,m)个解空间内分配,得解为
    x 0 + t ⋅ m g c d ( a , m ) , t ∈ 0 , 1 , 2 , . . . , g c d ( a , m ) x_0+t\cdot \frac{m}{gcd(a,m)},t\in{0,1,2,...,gcd(a,m)} x0+tgcd(a,m)m,t0,1,2,...,gcd(a,m)

    该式子中,特解为x=10 所以通解为 x ≡ 10 + 16 t ( m o d 3 ) 2 x\equiv 10+16t\pmod 32 x10+16t(mod3)2,解数为2,所以t=0,1

    Summary

    一次同余式求解较为简单,主要流程为:
    判断有无解->解数->化简->特解->通解
    在这些过程中,如果有大数,要灵活运用相关性质约简和求解.在此不赘述.

    展开全文
  • 同余方程组求解

    千次阅读 2016-08-07 02:57:57
    再考虑一下 A[i]*x=B[i](mod C[i])这类的同余方程求解 大体没什么区别 附上自打模版 ll mod(ll x,ll mm) { return (x%mm+mm)%mm; } pair,ll> Both(ll A[],ll B[], ll C[], int n) {//求解A[i]x=...

    第一种:模为互质的

    问题:
    一堆物品
    3个3个分剩2个
    5个5个分剩3个
    7个7个分剩2个
    问这个物品有多少个

    需要构造一个答案

    假设

    5*7*a%3=1

    3*7*b%5=1

    3*5*c%7=1

    乘上剩余个数

    2*5*7*a%3=2

    3*3*7*b%5=3

    2*3*5*c%7=2

    那么X=2*5*7*a+3*3*7*b+2*3*5*c,即为所求。

    再求个lcm(3,5,7) 的模,即为最小答案。

    typedef long long ll;
    ll a[4],m[4];
    ll ex_gcd(ll a,ll b,ll &x,ll &y)
    {
        if(b==0)
        {
            x=1;
            y=0;
            return a;
        }
        ll g=ex_gcd(b,a%b,x,y),t;
        t=x;
        x=y;
        y=t-(a/b)*y;
        return g;
    }
    ll China()
    {
        ll sum=1,ret=0;
        for(int i=0;i<n;i++) sum*=m[i];
        for(int i=0;i<n;i++)
        {
            ll Mi=sum/m[i],x,y;
            ex_gcd(Mi,m[i],x,y);
            ret=(ret+Mi*x*a[i])%sum;
        }
        return (ret%sum+sum)%sum;
    }
    

    第二类:模为不互质的(通过合并方程)



    吐槽一下,Mathtype不能插入中文,鼓捣了好久.. 

    然后自创模版

    ll mod(ll x,ll mm)
    {
        return (x%mm+mm)%mm;
    }
    pair<ll,ll> Both(ll B[], ll C[], int n)
    {//求解x=B[i](mod C[i]),总共n个线性方程组
        ll x,y,g,b=0,c=1;
        for(int i=0;i<n;i++)
        {
            ll aa=c,bb=B[i]-b,cc=C[i];
            g=ex_gcd(aa,cc,x,y);
            if(bb%g) return make_pair(-1,0);
            x=bb/g*mod(x,cc);
            b+=c*x;
            c*=cc/g;
            b=mod(b,c);
        }
        return make_pair(b,c);
    }

    再考虑一下 A[i]*x=B[i](mod C[i])这类的同余方程组的求解

    大体没什么区别

    附上自打模版

    ll mod(ll x,ll mm)
    {
        return (x%mm+mm)%mm;
    }
    pair<ll,ll> Both(ll A[],ll B[], ll C[], int n)
    {//求解A[i]x=B[i](mod C[i]),总共n个线性方程组
        ll x,y,g,a=1,b=0,c=1;
        for(int i=0;i<n;i++)
        {
            ll aa=c*A[i],bb=B[i]*a-b*A[i],cc=C[i]*a;
            g=ex_gcd(aa,cc,x,y);
            if(bb%g) return make_pair(-1,0);
            x=bb/g*mod(x,cc);
            b+=c*x;
            c*=a*cc/g;
            b=mod(b,c);
        }
        return make_pair(b,c);
    }


    a一直没变,可以简化成

    ll mod(ll x,ll mm)
    {
        return (x%mm+mm)%mm;
    }
    pair<ll,ll> Both(ll A[],ll B[], ll C[], int n)
    {//求解A[i]x=B[i](mod C[i]),总共n个线性方程组
        ll x,y,g,b=0,c=1;
        for(int i=0;i<n;i++)
        {
            ll aa=c*A[i],bb=B[i]-b*A[i],cc=C[i];
            g=ex_gcd(aa,cc,x,y);
            if(bb%g) return make_pair(-1,0);
            x=bb/g*mod(x,cc);
            b+=c*x;
            c*=cc/g;
            b=mod(b,c);
        }
        return make_pair(b,c);
    }

    以上都为了避免n=1的情况,所以初始都设了一个特殊的同余方程..

    展开全文
  • 求解线性同余方程

    2019-10-20 00:11:47
    求解线性同余方程 线性同余方程就是形如这样的方程: {a1x≡b1 (mod m1)a2x≡b2 (mod m2)               ...

    求解线性同余方程组

    线性同余方程组就是形如这样的方程组:

    { a 1 x ≡ b 1   ( m o d   m 1 ) a 2 x ≡ b 2   ( m o d   m 2 )                 ⋮ a n x ≡ b n   ( m o d   m n ) \begin{cases} a_1x\equiv b_1\ (mod\ m_1)\\ a_2x\equiv b_2\ (mod\ m_2)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots \\ a_nx\equiv b_n\ (mod\ m_n)\\ \end{cases} a1xb1 (mod m1)a2xb2 (mod m2)               anxbn (mod mn)

    与扩展中国剩余定理的证明类似,首先找出一个形如这样的方程: x ≡ b 0   ( m o d   m 0 ) x\equiv b_0\ (mod\ m_0) xb0 (mod m0)

    可以化为: x = b 0 + m 0 k 0 x=b_0+m_0k_0 x=b0+m0k0

    第一步可以假定 b 1 = 0 , m 1 = 1 b_1=0,m_1=1 b1=0,m1=1 ,代表解是所有的正整数。

    之后与方程组的第一个方程联立:

    { x ≡ b 0   ( m o d   m 0 ) a 1 x ≡ b 1   ( m o d   m 1 ) \begin{cases} x\equiv b_0\ (mod\ m_0)\\ a_1x\equiv b_1\ (mod\ m_1) \end{cases} {xb0 (mod m0)a1xb1 (mod m1)

    把一式带入二式得: a 1 ( b 0 + m 0 k 0 ) ≡ b 1   ( m o d   m 1 ) a_1(b_0+m_0k_0)\equiv b_1\ (mod\ m_1) a1(b0+m0k0)b1 (mod m1)

    a 1 b 0 + a 1 m 0 k 0 = b 1 + m 1 k 1 a_1b_0+a_1m_0k_0=b_1+m_1k_1 a1b0+a1m0k0=b1+m1k1

    a 1 m 0 k 0 = b 1 − a 1 b 0 + m 1 k 1 a_1m_0k_0=b_1-a_1b_0+m_1k_1 a1m0k0=b1a1b0+m1k1

    此时令 ( a , b ) (a, b) (a,b)表示 g c d ( a , b ) gcd(a,b) gcd(a,b),则有:

    a 1 m 1 ( a 1 m 0 , m 1 ) k 0 = b 1 − a 1 b 0 ( a 1 m 0 , m 1 ) + m 1 ( a 1 m 0 , m 1 ) k 1 \frac{a_1m_1}{(a_1m_0,m_1)}k_0=\frac{b_1-a_1b_0}{(a_1m_0,m_1)}+\frac{m_1}{(a_1m_0,m_1)}k_1 (a1m0,m1)a1m1k0=(a1m0,m1)b1a1b0+(a1m0,m1)m1k1

    (此时 ( a 1 m 0 , m 1 ) (a_1m_0,m_1) (a1m0,m1)一定要能够整除 b 1 − a 1 b 0 b_1-a_1b_0 b1a1b0,否则方程无解)

    所以有: a 1 m 0 ( a 1 m 0 , m 1 ) k 0 ≡ b 1 − a 1 b 0 ( a 1 m 0 , m 1 )   ( m o d   m 1 ( a 1 m 0 , m 1 ) ) \frac{a_1m_0}{(a_1m_0,m_1)}k_0\equiv \frac{b_1-a_1b_0}{(a_1m_0,m_1)}\ (mod\ \frac{m_1}{(a_1m_0,m_1)}) (a1m0,m1)a1m0k0(a1m0,m1)b1a1b0 (mod (a1m0,m1)m1)

    k 0 ≡ b 1 − a 1 b 0 ( a 1 m 0 , m 1 ) i n v ( a 1 m 0 ( a 1 m 0 , m 1 ) , m 1 ( a 1 m 0 , m 1 ) )   ( m o d   m 1 ( a 1 m 0 , m 1 ) ) k_0\equiv \frac{b_1-a_1b_0}{(a_1m_0,m_1)}inv(\frac{a_1m_0}{(a_1m_0,m_1)},\frac{m_1}{(a_1m_0,m_1)})\ (mod\ \frac{m_1}{(a_1m_0,m_1)}) k0(a1m0,m1)b1a1b0inv((a1m0,m1)a1m0,(a1m0,m1)m1) (mod (a1m0,m1)m1)

    k 0 = b 1 − a 1 b 0 ( a 1 m 0 , m 1 ) i n v ( a 1 m 0 ( a 1 m 0 , m 1 ) , m 1 ( a 1 m 0 , m 1 ) ) + y m 1 ( a 1 m 0 , m 1 ) k_0=\frac{b_1-a_1b_0}{(a_1m_0,m_1)}inv(\frac{a_1m_0}{(a_1m_0,m_1)},\frac{m_1}{(a_1m_0,m_1)})+y\frac{m_1}{(a_1m_0,m_1)} k0=(a1m0,m1)b1a1b0inv((a1m0,m1)a1m0,(a1m0,m1)m1)+y(a1m0,m1)m1

    代入高亮的上式:

    x = b 1 − a 1 b 0 ( a 1 m 0 , m 1 ) i n v ( a 1 m 0 ( a 1 m 0 , m 1 ) , m 1 ( a 1 m 0 , m 1 ) ) m 0 + y m 0 m 1 ( a 1 m 0 , m 1 ) + b 0 x=\frac{b_1-a_1b_0}{(a_1m_0,m_1)}inv(\frac{a_1m_0}{(a_1m_0,m_1)},\frac{m_1}{(a_1m_0,m_1)})m_0+y\frac{m_0m_1}{(a_1m_0,m_1)}+b_0 x=(a1m0,m1)b1a1b0inv((a1m0,m1)a1m0,(a1m0,m1)m1)m0+y(a1m0,m1)m0m1+b0

    x ≡ b 1 − a 1 b 0 ( a 1 m 0 , m 1 ) i n v ( a 1 m 0 ( a 1 m 0 , m 1 ) , m 1 ( a 1 m 0 , m 1 ) ) m 0 + b 0   ( m o d   m 0 m 1 ( a 1 m 0 , m 1 ) ) x\equiv \frac{b_1-a_1b_0}{(a_1m_0,m_1)}inv(\frac{a_1m_0}{(a_1m_0,m_1)},\frac{m_1}{(a_1m_0,m_1)})m_0+b_0\ (mod\ \frac{m_0m_1}{(a_1m_0,m_1)}) x(a1m0,m1)b1a1b0inv((a1m0,m1)a1m0,(a1m0,m1)m1)m0+b0 (mod (a1m0,m1)m0m1)

    此时可以将方程看作: x ≡ b   ( m o d   m ) x\equiv b\ (mod\ m) xb (mod m)

    其中 b = ( b 1 − a 1 b 0 ( a 1 m 0 , m 1 ) i n v ( a 1 m 0 ( a 1 m 0 , m 1 ) , m 1 ( a 1 m 0 , m 1 ) ) ) % m 1 ( a 1 m 0 , m 1 ) m 0 + b 0 b=(\frac{b_1-a_1b_0}{(a_1m_0,m_1)}inv(\frac{a_1m_0}{(a_1m_0,m_1)},\frac{m_1}{(a_1m_0,m_1)}))\%\frac{m_1}{(a_1m_0,m_1)}m_0+b_0 b=((a1m0,m1)b1a1b0inv((a1m0,m1)a1m0,(a1m0,m1)m1))%(a1m0,m1)m1m0+b0

    m = m 0 m 1 ( a 1 m 0 , m 1 ) m=\frac{m_0m_1}{(a_1m_0,m_1)} m=(a1m0,m1)m0m1

    到这里,式子里所有的值我们都知道了,并且得到了一个新的同余式。再把新的和其他的联立,依此循环,最终求出通解。

    代码

    //返回一个(b,m)的数对
    pair<int, int>linear_congruence(const vector<int>&A, const vector<int>&B, const vector<int>&M) {
    	//由于最开始没有任何限制,所以先把解设为表示所有整教的 x三0(mod 1)
    	int b = 0, m = 1;
    	for (int i = 0; i < A.size(); i++) {
    		int a = A[i] * m, b = B[i] - A[i] * b, 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);
    		b = b + m * t;
    		m *= M[i] / d;
    	}
    	return make_pair(x % m, m);
    }
    
    
    展开全文
  • //一次同余式求解 { if (!b) { x= 1 ; y= 0 ; return ; } exgcd(b,a%b,y,x); y-=a/b*x; } int main() { LL a,b,c,d,e; while (~ scanf ( "%lld%lld%lld%lld%lld" ,&a,&b,&c,&d,&e)) { LL x=d-c...
  • 线性同余方程又称一次同余方程,其形如ax≡b(mod n)。此方程有解当且仅当b能够被a与n的最大公约数整除,记作 gcd(a,n) | b。这时,如果 x0 是方程的一个解,那么所有的解可以表示为: {x0+kn/d|(k∈z)} 其中 d ...
  • 孙子定理是中国古代求解一次同余式组(见同余)的方法。是数论中一个重要定理。又称中国余数定理。一元线性同余方程问题最早可见于中国南北朝时期(公元5世纪)的数学著作《孙子算经》卷下第二十六题,叫做“物...
  • 中国剩余定理编程实现

    千次阅读 2017-02-16 14:55:30
    本文主要论述了中国剩余定理的背景,由来,证明方法,编程算法解决以及一些简单的应用,文章阐述了中国剩余定理的由来,介绍了他的几种解法.包括他的中国剩余定理研究,研究中国剩余定理的历史发展及在现代数论中的...
  • NOI数学:二次同余方程的解法

    千次阅读 2022-02-21 15:13:56
    C++ P1082 同余方程_ice_word的博客-CSDN博客_c++ 同余方程 二次同余方程的解 二次同余方程的解 - autoint - 博客园 算法导论-----数论-----计算x^2=1(mod n) 在区间[1,n-1]的解 - Inpeace7 - 博客园 【?】...
  • 孙子定理是中国古代求解一次同余式组(见同余)的方法。是数论中一个重要定理。又称中国余数定理。 原文 《孙子算经》 叫做“物不知数”问题,如下: 有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问...
  • 解线性同余方程

    2014-07-22 13:53:41
    前几天纠结了差不多一个多小时,终于把线性同余方程求解纠结清楚了……果然还是写下来怕自己忘记……其实qzone不适合写这种文章……不过反正也只有自己看就无所谓了…… 嗯……归纳一下 线性同余方程 ax≡b...
  • 原根与指标 ...作用:原根的求解只是求解高次同余方程时计算指标,判断是否有解。 定理5.2.1 设p是奇素数,则模p的原根存在,且有φ(p−1)φ(p-1)φ(p−1)个原根。 定理5.2.2 设p为奇素数,p-1的所有
  • C++之同余定理

    千次阅读 2019-05-20 19:50:39
    同余定理(一)同余定理的定义(二)同余定理的定理符号定义定理一:(三)同余定理相关定理欧拉函数推论(费马小定理)相关例题 (一)同余定理的定义 数论中的重要概念。给定一个正整数m,如果两个整数a和b满足a-b能够被m...
  • 在这一篇文章中,我将介绍函数式编程的基本概念,如何使用函数式编程的思想编写代码以及 Java Stream 的基本使用方法。 本文不会涉及到任何晦涩难懂的数学概念,函数式编程的理论以及函数式编程的高阶特性,譬如:...
  • 逻辑式编程语言极简实现(使用C#) - 1. 逻辑式编程语言介绍 相信很多朋友对于逻辑式编程语言,都有一种最熟悉的陌生人的感觉。一方面,平时在书籍、在资讯网站,偶尔能看到一些吹嘘逻辑式编程的话语。但另一方面,...
  • // 求解 0的解 #define MOD 76543 int hs[MOD],head[MOD],Next[MOD],id[MOD],top; void insert(int x,int y) { int k = x%MOD; hs[top] = x, id[top] = y, Next[top] = head[k], head[k] = top++; } int find...
  • C++编程风格约定

    2021-01-26 18:43:59
    本篇内容主要是参照谷歌C++标准规范,结合自身实际工作 及经验,整理一份适合平时C++开发的规则,规范自身C++编程规范。详细内容可参考1 函数1.1 参数顺序总述函数的参数顺序为: 输入参数在先, 后跟输出参数.说明C/...
  • 密码学笔记:离散对数求解相关算法实现

    千次阅读 多人点赞 2020-03-25 12:08:48
    离散对数求解相关算法计算方法介绍以及使用Python3实现...
  • 傻瓜函数式编程

    2019-10-28 00:09:58
    然后翻翻新闻还有那些技术网站上的更新,再过一遍编程论坛口水区里那些无聊的论战。最后从头把这些再看一次以免错过什么精彩的内容。然后就可以吃午饭了。饭饱过后,回来盯着IDE发一会呆,再看看邮箱,再去搞杯咖啡...
  • )readIndex 和 writeIndex 满足以下不变(invariant): 0 ≤ readIndex ≤ writeIndex ≤ data.size() Muduo Buffer 里有两个常数 kCheapPrepend 和 kInitialSize,定义了 prependable 的初始大小和 writable 的...
  • java 怎么解多元一次不定方程

    千次阅读 2021-03-17 14:20:01
    多元一次不定方程的强力算法---同余筛数法uniqueleion6152018-10-24Python100例——第五章----不定方程的解wdt338516542013-07-19高斯消元求解多元一次方程nikelong021632016-03-26二元一次不定方程的快速解法...
  • 同余问题1(超详细!!!)

    千次阅读 2019-09-23 07:16:18
    同余基本概念 剩余系 欧拉函数 欧拉函数φ(n)表示1~n中所有与n互质的数。比如1~8中与8互质的数有1,3,5,7,所以φ(8)=4。 公式1:如果p是素数,有φ(p)=p-1。 公式2(积性):如果(a,b)=1,有φ(a...
  • 数值分析里面经常会涉及到用MATLAB程序实现用列主元消去法分别解方程Ax=b具体的方法和代码以如下方程(3x3矩阵)为例进行说明:用列主元消去法分别解方程Ax=b,用MATLAB程序实现:(1)1、 实现该方程的解的MATLAB...
  • 同余

    2021-04-13 16:17:07
      同余,是数论中一个特别重要的一部分,而且编程中需要用到数论的大部分都是同余相关的问题。所以本篇博客就来介绍一下关于同余的一些东西。 文章目录模运算 模运算   同余有一个十分基础的运算,叫做取模。而...
  • 【算法】同余问题

    2019-08-09 17:42:03
    给定一个正整数m,如果两个整数a和b满足a-b能够被m整除,即(a-b)/m得到一个整数,那么就称整数a与b对模m同余,记作a≡b(mod m),并称该式子为同余式。 2.整数的集合被分为m个不同的集合,这些集合被称为模m剩余类...
  • suchaoshanhun722013-07-013元一次方程(牛顿迭代法求方程的根)dd_zhouqian21972014-07-15python简单的三元一次方程求解chen104224661214712018-11-05oldguncm37652008-11-05高斯消元求解多元一次方程nikelong...
  • 针对引理1,通过同余式本身的特点,都十分易证,随后再基于引理1,引理2也不难得证。这里便不再累述。 有了这两个引理做铺垫,下面便可以开始费马小引理的证明了。  构造素数p的完全剩余系P = {1,2,3,……p-1}。 ...
  • 3.2 求解不定方程和同余方程的实验范例 公约数和同余问题是初等数论的两个核心内容,是求解许多...2)介绍求解同余方程和同余方程的基本方法。3.2.1 计算最大公约数和不定方程整数a和b的最大公约数可通过欧几里得...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,011
精华内容 1,604
关键字:

编程实现同余式组的求解