拓展欧几里得,中国剩余定理,容斥原理

拓展欧几里得

裴蜀定理

对于任意整数a,b，存在一对整数x,y，满足ax + by = gcd(a,b)

拓展欧几里得就是求出裴蜀定理解的算法

例题：

给定 n 对正整数 ai,bi，对于每对数，求出一组 xi,yi使其满足 ai×xi+bi×yi=gcd(ai,bi)

输入格式

第一行包含整数 n。

接下来 n 行，每行包含两个整数 ai,bi

输出格式

输出共 n 行，对于每组 ai,bi，求出一组满足条件的 xi,yi，每组结果占一行。

本题答案不唯一，输出任意满足条件的 xi,yi 均可。

数据范围

1≤n≤10^5^
1≤ai,bi≤2×10^9^

输入样例：

2
4 6
8 18

输出样例：

-1 1
-2 1

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T -- > 0){
            int a = sc.nextInt();
            int b = sc.nextInt();

            Int x = new Int();
            Int y = new Int();

            exgcd(a, b, x, y);

            System.out.println(x.v + " " + y.v);
        }

        sc.close();
    }

    private static int exgcd(int a, int b, Int x, Int y){
        if (b == 0){
            x.v = 1;y.v = 0;
            return a;
        }

        int gcd = exgcd(b, a % b, y, x);
        y.v -= a / b * x.v;

        return gcd;
    }
}

class Int{
    int v;

    public Int() {
    }

    public Int(int v) {
        this.v = v;
    }
}

线性同余方程

给定整数a，b，m，求一个整数x满足a * x ≡ b (mod m)，或者给出无解。因为未知数的指数为1，所以我们称之为一次同余方程，也称线性同余方程。

例题：

给定 n 组数据 ai,bi,mi对于每组数求出一个 xi，使其满足 ai×xi≡bi(modmi) 如果无解则输出 impossible。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一组数据 ai,bi,mi

输出格式

输出共 n 行，每组数据输出一个整数表示一个满足条件的 xi，如果无解则输出 impossible。

每组数据结果占一行，结果可能不唯一，输出任意一个满足条件的结果均可。

输出答案必须在 int 范围之内。

数据范围

1≤n≤10^5^
1≤ai,bi,mi≤2×10^9^

输入样例：

2
2 3 6
4 3 5

输出样例：

impossible
-3

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n -- > 0){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int m = sc.nextInt();

            Int x = new Int();
            Int y = new Int();

            int d = exgcd(a, m, x, y);
            if (b % d == 1) System.out.println("impossible");
            else System.out.println((long)b / d * x.v % m);
        }

        sc.close();
    }

    private static int exgcd(int a, int b, Int x, Int y){
        if (b == 0){
            x.v = 1;y.v = 0;
            return a;
        }

        int gcd = exgcd(b, a % b, y, x);
        y.v -= a / b * x.v;

        return gcd;
    }
}

class Int{
    int v;

    public Int() {
    }

    public Int(int v) {
        this.v = v;
    }
}

中国剩余定理

在《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二（除以3余2），五五数之剩三（除以5余3），七七数之 剩二（除以7余2），问物几何？”这个问题称为“孙子问题”，该问题的一般解法国际上称为“中国剩余定理”。

QQ截图20220306102529

例题：

给出 n 个同余方程 x ≡ ri (mod pi)的 pi, ri，求出 x 的最小非负整数解。若无解则输出”-1”（没有引号）。

输入格式

第一行包含一个正整数 n(1 ≤ n ≤ 10^5^)，表示同余方程的个数。

接下来 n 行，每行两个正整数 pi,ri(1 ≤ pi ≤ 10^12^,0 ≤ ri＜p)。

数据保证所有 p 的最小公倍数不超过10^18^。

注意运算过程中的乘法溢出。

输出格式

输出同余方程的最小非负整数解，若无解输出”-1”（没有引号）。

输入样例：

2
8 7
11 9

输出样例：

31

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    static BigInteger a[] = new BigInteger[100005];
    static BigInteger m[] = new BigInteger[100005];;
    static int n;
    static BigInteger x,y;
    static BigInteger v0 = BigInteger.valueOf(0);
    static BigInteger v1 = BigInteger.valueOf(1);
    
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            n = sc.nextInt();
            for(int i = 1; i <= n; ++i) {
                m[i] = sc.nextBigInteger();
                a[i] = sc.nextBigInteger();
            }
            excrt();
        }
    }
    
    private static BigInteger exgcd(BigInteger a,BigInteger b)
    {
        if(b.equals(v0)) {
            x = v1;
            y = v0;
            return a;
        }
        BigInteger r = exgcd(b,a.remainder(b));
        BigInteger z = x;
        x = y;
        y = z.subtract(a.divide(b).multiply(y));
        return r;
    }

    private static void excrt() {
        BigInteger M = m[1], A = a[1], t, d;
        for(int i = 2; i <= n; ++i) {
            d = exgcd(M, m[i]);
            if(a[i].subtract(A).remainder(d).compareTo(v0) != 0) {
                System.out.println("-1");
                return;
            }
            x = x.multiply((a[i].subtract(A)).divide(d));
            t = m[i].divide(d);
            x = (x.remainder(t).add(t)).remainder(t);
            A = M.multiply(x).add(A);
            M = M.divide(d).multiply(m[i]);
            A = A.remainder(M);
        }
        A = A.remainder(M).add(M).remainder(M);
        System.out.println(A);
    }
}

容斥原理

QQ截图20220306111955

330px-Inclusion-exclusion.svg

例题：

给定一个整数 n 和 m 个不同的质数 p1,p2,…,pm。

请你求出 1∼n 中能被 p1,p2,…,pm 中的至少一个数整除的整数有多少个。

输入格式

第一行包含整数 n 和 m。

第二行包含 m 个质数。

输出格式

输出一个整数，表示满足条件的整数的个数。

数据范围

1≤m≤16
1≤n,pi≤10^9

输入样例：

10 2
2 3

输出样例：

7

import java.util.Scanner;

public class Main {
    static int N = 20;
    static int q[] = new int[N];
    static int n,m;
    static long res;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            q[i] = sc.nextInt();
        }

        for (int i = 1; i < 1 << m; i++) {
            int t = 1,cnt = 0;

            for (int j = 0; j < m; j++) {
                if ((i >> j & 1) == 1){
                    if ((long)t * q[j] <= n){
                        t *= q[j];
                        cnt ++;
                    }
                    else {
                        t = -1;
                        break;
                    }
                }
            }

            if (t != -1){
                if (cnt % 2 == 1) res += n / t;
                else res -= n / t;
            }
        }

        System.out.println(res);

        sc.close();
    }
}