基础数论

素（质）数

1）试除法判断素数

    boolean isPrime(int n){
        if( n == 1) return false;
        for(int i = 2 ; i <= n/i ; i ++){
            if( n % i == 0 ) return false;
        }
        return true;
    }

2）分解质因数

1)分解 n 的质因数

   void devide(int n ){
        for(int i = 2 ; i <= n / i ; i ++){
            if(n % i  == 0 ){
                int cnt = 0;
                while( n % i  == 0){
                    cnt++;
                    n /= i;
                }
                System.out.println(i +" "+ cnt);
            }
        }
        if( n > 1) System.out.println(n +" "+ 1);
    }

2)分解 n ! 的质因数

 for(int i = 2 ; i <= n ;i ++ )
    {
       if( !st[i] ) primes[cnt ++] = i;
           
       for(int j = 0 ; primes[j] <= n / i ; j ++)
       {
           st[primes[j] * i] = true;
           if(i % primes[j] == 0) break;
       }
    }

    for(int i = 0 ; i < cnt ; i ++ )
    {
        int p = primes[i];
        int count = 0;
        for(int j = n ; j ; j /= p )  count += j / p;
        
        cout << p <<' ' << count << endl;
    }

筛质数

    int primes(int n ){
        int[] primes = new int[n];
        boolean[] st = new boolean[n+1];
        int cnt = 0;
        for(int i = 2 ; i <= n ;i ++){
            if( !st[i] ) primes[cnt++] = i;
            for(int j = 0 ; primes[j] <= n / i ; j++ ){
                st[ primes[j] * i] = true;
                if( i % primes[j] == 0 ) break;
            }
        }
        return cnt;
    }

筛区间[L ,R]之间的质数
1）找出1-50000（sqrt(Integer.MAX)）之间的所有质因子
2）对于1-50000中的每个质数 p ，将[L ,R]中所有p的倍数筛掉（至少2倍）

typedef long long LL;

const int N = 1000010;

int primes[N] , cnt;
bool st[N];

void init(int n )
{
    for(int i = 2 ;i <= n ;i ++ )
    {
        if(!st[i]) primes[cnt++] = i;
        for(int j = 0 ; primes[j] <= n / i ; j ++ )
        {
            st[primes[j] * i] = true;
            if( i % primes[j] == 0) break;
        }
    }
}

int main()
{
    cin >> l >> r ;
    init(50000);

    memset(st ,0 ,sizeof st);
    for(int i = 0 ; i < cnt ; i ++)
    {
        LL p = primes[i];            
        for(LL j = max( p * 2 , (l + p - 1) / p * p ) ; j <= r ; j += p )
           st[j - l] = true;   
     }

    cnt = 0;
    for(int i = 0 ; i <= r - l ; i ++ )
        if( !st[i] && i + l >= 2) primes[cnt++] = i + l;

    return 0;
}

约（因）数

1）试除法

  void divisor(int n){
        ArrayList<Integer> left = new ArrayList<>();
        ArrayList<Integer> right =new ArrayList<>();
        for(int i = 1 ; i <= n / i ;i ++){
            if( n % i == 0 ){
              left.add(i);
              if( i !=  n / i ) right.add( n / i);
            } 
        }
        for(Integer i : left)System.out.print(i+" ");
        for(int i = right.size() - 1 ; i >= 0 ; i--)System.out.print(right.get(i)+" ");
    }

2）约数个数
n 个正整数乘积的约数个数
公式：
n=p1^a1 * p2^a2 * p3^a3 … pk^ak
约数个数：(a₁+1)(a₂+1)(a₃+1)…(ak+1)

import java.util.*;

public class Main{
    
    static int mod = (int)1e9 + 7;
    static HashMap<Integer,Integer> map = new HashMap<>();
    
    static void get_dividsor(int n ){
        
        for(int i = 2 ; i <= n / i ;i ++){
            if(n % i == 0){
                int cnt = 0;
                while( n % i == 0){
                 cnt++;
                 n /= i;
                }
                map.put(i , map.getOrDefault(i , 0) + cnt);
            }        
        }
        if(n > 1)map.put(n , map.getOrDefault(n , 0) + 1);
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while( n -- > 0){
            int x = sc.nextInt();
            get_dividsor(x);
        }
        
        long ans = 1;
        for(int cnt : map.values() ){
            ans = ans * (cnt+1) % mod; //组合的思想 ，比如cnt个2 , 可以选择0 ~ cnt 个 2 
        }
        System.out.println(ans);
    }
}

3）约数之和
n个正整数的乘积的约数之和
公式：
n=p1^a1 * p2^a2 * p3^a3 … pk^ak
约数和：f(n)=(p1^0 + p1^1 + p1^2 +…p1^a1 )(p2^0 +p2^1 +p2^2 +…p2^a2 )…(pk^0 +pk^1 +pk^2 +…pk^ak ）

import java.util.*;

public class Main{
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        HashMap<Integer , Integer> map = new HashMap<>();
        int mod = (int)1e9 +7;
        while(n-- > 0){
            int x = sc.nextInt();
            for(int i = 2; i <= x/i ;i ++){
                while(x % i == 0){
                    map.put(i , map.getOrDefault(i , 0) + 1);
                    x /= i;
                }
            }
            if( x > 1) map.put(x , map.getOrDefault(x , 0) + 1);
        }
        long res = 1;
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            int p = entry.getKey() , a = entry.getValue();
             // 1 + p^1 + p^2 +...+p^a
             // 1 + p(1 + p + ...+p^a-1 )
             // 1 + p(1 + p(1 + p + .. + p^a-2)
             // ...
             // 1 + p(1 + p(1 + p(1 +P((...(1+p) ))))) a-1个括号
             //从最内层往外层算
            long t = 1;
            for(int i = 1 ; i <= a ; i++){
                t = (t*p+1) % mod;
            };
            res = res * t % mod;
        }
        System.out.println(res);
    }
}

4）最大公约数
欧几里得算法（辗转相除法）

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

4）最小公倍数
欧几里得算法（辗转相除法）

    int lcm(int a ,int b){
        return a * b / gcd(a , b );
    }

欧拉函数

1∼N 中与 N 互质的数的个数被称为欧拉函数，记为 ϕ(N)。
若在算数基本定理中， $N=p_1^{a_1} p_2^{a_2} …p_m^{a_m}$ 则：
$ϕ(N) = N×\frac{p_1−1}{p_1}×\frac{p_2−1}{p_2}×…×\frac{p_m−1}{p_m}$

若 n为质数，则 φ(i) = n - 1 ，因为 1~ n-1中每个数都和 n 互质
p为质数，已知 φ(i) = i * x ，求 φ(p * i) ：
- 若 p 是 i 的约数，则 φ(p * i) = p * i * x = p * φ(i)
  因为 p 是 i 的约数，所以在求 φ(i) 的公式中已经乘了 (p - 1) / p ，虽然 p 也是 p * i 的约数，但在求某个数的欧拉函数的公式中，只看约数，而不看约数的次数。
- 若 p 不是 i 的约数，则
  φ(i * p) = i * p * x * (p - 1) / p = i * x * (p - 1) = φ(i) * (p - 1)

1）求某个数的欧拉函数

    int euler(int n ){
        int res = n;
        for(int i = 2 ; i <= n / i;i ++ ){
            if( n % i == 0 ){
                while( n % i == 0){
                    n /= i ;
                }
                res = res / i * (i - 1); //这里要先除 ，因为（i-1）/ i 不能整除
            }
        }
        if(n > 1) res = res / n *(n - 1);
        return res;
    }

2）求 1 - n 之间的所有的数的欧拉函数之和

  long get_euler(int n){
        int[] primes = new int[n+1];
        int[] phi = new int[n+1];
        int idx = 0;
        boolean[] st = new boolean[n+1];
        
        for(int i = 2 ;i <= n ;i ++ ){
            if(!st[i]){
                primes[idx++] = i;
                phi[i] = i-1;
            }
            
            for(int j = 0 ; primes[j] <= n/i ;j ++){
                st[i*primes[j]] = true;
                if( i % primes[j] == 0 ){
                    phi[i * primes[j] ] = phi[i] * primes[j];
                    break;
                }
                phi[i * primes[j]] = phi[i] * (primes[j]-1);
            }
        }
        long res = 1;//phi[1] = 1
        for(int i = 2 ; i<=n;i++)res += phi[i];
        return res;
    }

逆元

1）快速幂 $a_i^{b_i} mod p_i$

    long qmi(long a ,long k ,long p){
        long res = 1;
        while( k != 0 ){
            if( (k & 1) == 1 ) res = res * a % p;
            k = k >> 1;
            a = a * a % p;
        }
        return res ;
    }

快速幂求逆元

$b * x \equiv 1 \pmod{p}$
若 p 为质数，费马小定理 $b ^{p-1} \equiv 1 \pmod{p}$ ，即 $b * b^{p-2} \equiv 1 \pmod{p}$ ，所以 b 的逆元为 $b^{p-2} \pmod p$
b 不能为 p的倍数，否则 $b^{p-2} \equiv 0 \pmod p$

    x = qmi(b,p-2,p) //调用上面求快速幂的函数即可

若 p 不是质数，可以用扩展欧几里得算法求逆元：
a有逆元的充要条件是a与p互质，所以gcd(a, p) = 1
假设a的逆元为x，那么有a * x ≡ 1 (mod p)
等价：ax + py = 1
exgcd(a, p, x, y)

扩展欧几里得

扩展欧几里得算法用于求解 ax + by = gcd(a , b)的解
当 b = 0 时 , ax + by = a ，故 x = 1 , y = 0
当 b ≠ 0 时，
因为 gcd(a , b) = gcd(b , a % b)
而 $b x' + (a \% b)y' = gcd(b , a \% b)$
$bx′+(a−⌊a/b⌋∗b)y′=gcd(b,a\%b)$
$ay′+b(x′−⌊a/b⌋∗y′)=gcd(b,a\%b)=gcd(a,b)$
故而
$x=y′,y=x′−⌊a/b⌋∗y′$

    static int x ,y; //a , b互质时 ， x 即为 a 的逆元
    
    static int exgcd(int a ,int b ){
        if(b == 0){
            x = 1; y = 0;
            return a;
        }
        int d = exgcd(b , a % b);
        int t = y;
        y = x - a / b * y;
        x = t ;
        return d;
    }

2）线性同余 $a* x = b \pmod{m}$

扩展欧几里得可以求解 ax + by = gcd(a , b)
$a * x = b \pmod{m}$ ---> $a * x = b + k*m$ --> $a * x - m*k = b$
即 $a * x + my= b$

使用扩展欧几里得求得 $a * x_0 + m *y_0= gcd(a_ , m)$
1）裴蜀定理( Bezout )，当 $b \% gcd(a , m) = 0$ ，原式有解，且 $\frac{x}{x_0} = \frac{b}{gcd(a , m)}$ ，故 $x = x_0 * \frac{b}{gcd(a , m)} \% m$ ( % m 是要求 x 也在 1 - m直之间)
2）当 $b \% gcd(a , m) \neq 0$ ，原式无解

 public class Main{
    
    static int x , y;
    
    static int exgcd(int a ,int b){
        if(b == 0){
            x = 1; y = 0;
            return a;
        }
        int d = exgcd(b , a % b);
        int t = y;
        y = x - a/b *y;
        x = t;
        return d;
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while(n -- > 0){
            int a = sc.nextInt() , b = sc.nextInt() , m = sc.nextInt();
            int d = exgcd(a ,m);
            if( b % d == 0) System.out.println( (long)x * b / d % m );
            else System.out.println("impossible");
        }
    }
}

3 欧拉定理

若 a , n为正整数，且 a , n互质
$a^{\phi(n)} = 1 \pmod{n}$

中国剩余定理

以两个式子 x = m1 (mod) a1 ，x = m2 (mod) a2开始推导
$x=k_1∗a_1+m_1$
$x=k_2∗a_2+m_2$
即 $k_1 a_1 - k_2 a_2 = m_2 - m_1 ,其中 d = exgcd(a1 , - a2)$

加上 $k \frac{a_2a_1}{d}并减去k \frac{a_2a_1}{d}$ ，得
$k_1 a_1 +k \frac{a_2a_1}{d} - k_2 a_2 - k\frac{a_1 a_2}{d} = m_2 - m_1$
$(k_1 + k \frac{a_2}{d}) a_1 - (k_2 + k \frac{a_1}{d}) a_2 = m_2 - m_1$
即 $k_1 = k_1 + k\frac{a_2}{d} ，k_2 = k_2 + k \frac{a_1}{d}$

则 $x = (k_1+ k\frac{a2}{d} ) a_1 + m_1 ，即 x = k_1a_1 + m_1 + k\frac{a_1a_2}{d} ,其中 \frac{a_1 a_2}{d} = a_1 ,a_2的最小公倍数$
$令 x_0 = k_1 a_1 +m_1 ,a= \frac{a_1 a_ 2}{d}，可得 x = x_0 + k a$
可以把 $x = x_0 + k a$ 继续和后面的式子合并，最后的形式就是一个 $x = x_0 + k a$ 样的式子
即答案 $x = x_0 \pmod{a} ，即x_0在1-a之间的余数$

注意的是：在每合并两个式子的时候都需要判断是否满足 $gcd(a_1 , -a_2) | (m2 - m1)$

import java.util.*;

public class Main{
    
    static long x , y;
    
    static long exgcd(long a ,long b){
        if(b == 0){
            x = 1 ; y = 0;
            return a;
        }
        long d = exgcd(b , a % b);
        long t = y;
        y = x - a / b * y;
        x = t;
        return d;
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long a1 = sc.nextLong() ,m1 = sc.nextLong();
        boolean has_answer = true;
        while(--n > 0){
            long a2 = sc.nextLong() , m2 = sc.nextLong();
            long d = exgcd(a1 , -a2);
            if( (m2 - m1) % d != 0 ){
                has_answer = false;
                break;
            }
            long t = (m2 - m1) / d;
            long mod = Math.abs( a2 / d ); //   a2  / d不知道正负
            x = (x * t % mod + mod) % mod; // k1 = k1 + k*a2/d，模的是 abs(a2 / d),让 k1尽可能的小 
            m1 = x * a1 + m1; //新的 X0
            a1 = Math.abs(a1 / d *a2); //不知道正负，所以取绝对值
        }
        if(!has_answer) System.out.println("-1");
        else System.out.println( (m1% a1 + a1) % a1 ); //取的是正数
    }
}

CRT.png

组合数

1）通过组合的思想求 $C_a^b = \frac{a!}{ (a-b)! b! } \pmod {1e^9 + 7}$
数据范围特点：n比较大，a , b不大
1 ≤ n ≤ 10000,
1 ≤ b ≤ a ≤ 2000

    static int N = 2010;
    static int[][] g = new int[N][N];
    static int mod = (int)1e9 + 7;
    
    static{
        for(int i = 0 ; i < N ; i ++)
            for(int j = 0 ; j <= i ;j ++)
                if( j == 0 ) g[i][j] = 1;
                else g[i][j] = (g[i-1][j-1] + g[i-1][j]) % mod;
    }

2）使用公式求： $C_a^b = \frac{a!}{ (a-b)! b! } \pmod {1e^9 + 7}$
数据范围特点：n比较大，a，b比较大，对 1e9 + 7去模
1 ≤ n ≤ 10000,
1 ≤ b ≤ a ≤ 100000
主要过程是先预处理出 1-100000的阶乘，阶乘的逆元，然后使用公式计算

    static int qmi(int a ,int k ,int p){
        long res = 1;
        while( k!= 0 ){
            if( (k&1) == 1 ) res = res * a % mod;
            k = k >> 1;
            a = (int)((long)a * a % mod);
        }
        return (int)res;
    }

    static int N = 100010;
    static long[] fact = new long[N] , infact = new long[N];
    static int mod = (int)1e9 + 7;
    
    static{
        fact[0] = infact[0] = 1;
        for(int i = 1 ; i < N ; i ++ ){
            fact[i] = fact[i-1] * i % mod;
            infact[i] = infact[i-1] * qmi( i , mod-2 , mod) % mod ; // mod 是质数，费马小定理
        }
            
    }
//最后：
 ans =  fact[a] * infact[a - b] % mod  * infact[b] % mod

3）Lucas定理求 $C_a^b \pmod p$
数据范围特点：n 很小，a , b非常大，p为质数(比a还小)
1 ≤ n ≤ 20,
1 ≤ b ≤ a ≤ 10^18,
1 ≤ p ≤ 10^5,

lucas定理：
$C_a^b \pmod p = C_{a \% p}^{b \% p} * C_{a / p} ^{b / p} \pmod p$

当 a 或者 b 大于 p时，递归求解，当 a < p && b < p时，直接使用公式求解

    static long qmi(long a ,long k ,long p){
        long res = 1;
        while( k != 0){
            if( (k&1) == 1 ) res = res * a % p;
            k >>= 1;
            a = a * a % p;
        }
        return res;
    }
    
    static long C(long a ,long b ,long p){
        long res = 1;
        for(long i = a , j = 1; j <= b ; i -- , j ++ ){
            res = res * i % p;
            res = res * qmi(j , p-2 , p) % p;
        }
        return res;
    }
    
    static long lucas(long a , long b ,long p){
        if( a < p && b < p ) return C(a , b , p);
        return C(a % p, b % p , p) * lucas(a / p , b / p , p) % p;
    }

ans = lucas(a , b ,p)

4）质数线性筛法 + 高精度乘法求 $C_a^b$ ，没有取模
数据范围特点：不对结果取模，结果非常大
1 ≤ b ≤ a ≤ 5000

import java.util.*;

public class Main{
    
    static int N = 5010;
    static int[] primes = new int[N];
    static int[] sum = new int[N];
    static boolean[] st = new boolean[N];
    static int cnt = 0;
    
    static void get_primes(int n ){
        for(int i = 2 ; i <= n ;i ++ ){
            if( !st[i] ) primes[cnt ++ ] = i;
            for(int j = 0 ; primes[j] <= n / i ; j ++ ){
                st[ primes[j] * i ] = true;
                if( i % primes[j] == 0 ) break;
            }
        }
    }
    
    static int get(int x , int p){
        int res = 0;
        while( x != 0){
            res += x / p;
            x /= p;
        }
        return res;
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt() , b = sc.nextInt();
        get_primes(a);
        for(int i = 0 ; i < cnt ;i ++){
            int p = primes[i];
            sum[i] = get(a , p) - get(b , p) - get(a - b , p);
        }
        
        ArrayList<Integer> res = new ArrayList<>();
        res.add(1);
        for(int i = 0 ; i < cnt ;i ++)
            for(int j = 0 ; j < sum[i] ; j ++)
                res = mul(res , primes[i]);
        
        for(int i = res.size()-1 ; i >= 0 ;i --) 
            System.out.print( res.get(i) );
        
    }
    
    
    static ArrayList<Integer> mul(ArrayList<Integer> A ,int b){
        ArrayList<Integer> res = new ArrayList<>();
        int t = 0;
        for(int i = 0; i < A.size() ; i ++){
            t = A.get(i) * b + t;
            res.add( t % 10 );
            t /= 10;
        }
        while( t != 0){
            res.add( t % 10 );
            t /= 10;
        }
        return res;
    }
}

5）卡特兰数
$f(n) = \frac{C_{2n}^n}{ n + 1 } ,$
变形： $f(n) = C_{2n}^n - C_{2n}^{n-1}$

满足递推式： f(n) = f(1) * f(n-1) + f(2) * f(n-2) + ....
有一种性质：任意前缀中某种东西 >= 另外一种东西

import java.util.*;

public class Main{
    
    static long qmi(long a ,long k , int p){
        long res = 1;
        while(k!=0){
            if( (k&1) == 1 ) res = res * a % p;
            k =  k >> 1;
            a = a * a % p;
        }
        return res;
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int mod = (int)1e9 + 7;
        int a = 2*n , b = n;
        long ans = 1;
        for(int i = a , j = 1; i > a-b;i-- ,j++){
          ans = ans * i % mod;  
          ans = ans * qmi(j , mod-2 ,mod) % mod;
        } 
        ans = ans * qmi(n + 1 , mod-2 ,mod) % mod;
        System.out.println(ans);
    }
}

高斯消元

线性方程组

import java.util.Scanner;

public class Main{
    
    static int n , N = 110;
    static double[][] g = new double[N][N];
    static double eps = 1e-6;
    
    static int gauss(){
        int c , r;
        for(c = 0 , r = 0 ; c < n ; c ++){
            //找主元
            int t = r;
            for(int i = r ; i < n ;i ++)
                if( Math.abs(g[i][c]) > Math.abs(g[t][c]) )
                    t = i;
                    
            if( Math.abs( g[t][c] ) < eps ) continue;
            
            //交换
            for(int i = c ; i <= n ;i ++)  swap(t ,i ,r ,i);
            //归一化            
            for(int i = n ; i >= c ; i --) g[r][i] /= g[r][c];
            //消元
            for(int i = r+1 ; i < n ;i ++)
                if( Math.abs( g[i][c] ) > eps )
                    for(int j = n ; j >= c ; j --)
                        g[i][j] -= g[i][c] * g[r][j];
                        
            r++;
        }
        
        if( r < n){
            for(int i = r ; i < n ;i ++)
                if( Math.abs(g[i][n]) > eps ) return 2; //无解
            return 1;//无限解
        }
        //求解
        for(int i = n - 1 ; i >= 0 ;i --)
            for(int j = i+1 ; j < n ; j ++ )
                g[i][n] -= g[i][j] * g[j][n];
        
        return 0;
    }
    
    static void swap(int x1 ,int y1 ,int x2 ,int y2){
        double t = g[x1][y1];
        g[x1][y1] = g[x2][y2];
        g[x2][y2] = t;
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n  = sc.nextInt();
        for(int i = 0 ; i < n ;i ++)
            for(int j = 0 ; j <= n ;j ++)
                g[i][j] = sc.nextDouble();
                
        
        int ans = gauss();
        if(ans == 2) System.out.println("No solution");
        else if(ans == 1) System.out.println("Infinite group solutions");
        else for(int i = 0 ; i < n ;i ++) System.out.println( String.format("%.2f" ,g[i][n] ) );
    }
}

异或方程组

import java.util.*;

public class Main{
    
    static int n , N = 110;
    static int[][] a = new int[N][N];
    
    static int gauss(){
        int r , c;
        //从第一列开始遍历
        for(r = c = 0 ; c < n ; c ++){
            
            int t = r; //选择第 c列不为0的行
            for(int i = r ; i < n ;i ++){
                if( a[i][c] != 0 )
                    t = i;
            }
            
            //表示该列所有行（r及以下）都为0
            if( a[t][c] == 0 ) continue;
            
            //把不为0的行和当前行交换
            for(int i = c ; i < n +1 ; i ++ ) swap(r , i , t , i );
           
            //消元
           for(int i = r + 1 ; i <= n ;i ++)
              for(int j = n + 1 ; j >= c ; j -- )
                  a[i][j] ^= a[i][c] & a[r][j]; 
            r ++ ;
        }
        
        if( r < n){
            for(int i = r; i < n ;i ++)
                if(a[i][n] != 0) 
                    return 2;
            return 1;
        }
        
        for(int i = n-1 ; i >= 0 ;i --){
            for(int j = i+1 ; j < n; j ++){
                a[i][n] ^= a[i][j] & a[j][n]; // j表示的是第i行第j个数
                                            // 对应的为1的行在第j列
            }
        }
        return 0 ;
    }
    
    static void swap(int x1 ,int y1 ,int x2 ,int y2){
        int t = a[x1][y1];
        a[x1][y1] = a[x2][y2];
        a[x2][y2] = t ;
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for(int i = 0 ; i < n ;i ++)
            for(int j = 0 ; j < n + 1 ;j ++)
                a[i][j] = sc.nextInt();
                
        int res = gauss();
        if( res == 0 ){
            for(int i = 0 ; i < n ; i ++ ) System.out.println(a[i][n]); 
        }else if( res == 1 ){
            System.out.println("Multiple sets of solutions");
        }else{
            System.out.println("No solution");
        }
    }
}

容斥原理

容斥原理：

记 S_i 为 1-n中能整除 p_i的集合

，那么根据容斥原理，所有数的个数为各个集合的并集，计算公式如下：

\bigcup_{i=1}^{m} S_i = S_1 + S_2 +\cdots +S_I - (S_1 \bigcap S_2 +S_1 \bigcap S_3 + \cdots +S_{m-1} \bigcap S_m) + S_1 \bigcap S_2 \bigcap S_3 + \cdots

实现思路
1）实际上并不需要知道每个集合里面的具体的元素是什么，只需要知道集合的大小，大小为

| S_i| = n / p_i

。

2） $p_i$ 为质数，这些数的乘积就是他们的最小公倍数，所以交集的大小就是 n除以它们的乘积，交集的大小为 $S_1 \bigcap S_2 = n / (p_1 * p_2)$

3）使用二进制作为集合状态的表示，比如有 4 个质数， m = 4，所以需要 4 位二进制进行表示，每个二进制位表示集合 $S_i$ 是否被选中，例如： $\begin{matrix} m=4 \\ \overbrace{ 1101 }\end{matrix}$ ，表示的集合 $S_1 , S_2 , S_4$ 被选中，这个集合的元素个数为 $n / (p_1 * p _2 * p _4)$ ，在公式中，系数为 $(-1)^{k-1}$ ，k为选中的集合个数，即选中奇数个集合前面的系数为1，偶数个集合系数为 -1。

实现代码：

import java.util.*;

public class Main{
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] p = new int[m];
        for(int i = 0; i < m ;i ++)p[i] = sc.nextInt();
        
        int res = 0;
        //枚举从00001到 11111(m个1)的每一个集合状态，（至少选中一个集合） 
        for(int i = 1 ; i < 1 << m ; i ++){  //
            int t = 1; //选中的集合对应的乘积
            int s = 0;//选中的集合数量
            
            //枚举当前状态的每一位
            for(int j = 0; j < m ; j ++){
                //第j个集合被选中了
                if( (( i>>j ) & 1 ) == 1 ){
                    //乘积大于n , 则 n/t = 0 ，跳出这轮循环
                    if( (long) t * p[j] > n ){
                        t = -1;
                        break;
                    }
                    s++;
                    t *= p[j];
                }    
            }
    
            if(t == -1) continue;
            
            if( (s&1) == 1 ) res += n/t; //选中奇数个集合，系数为1
            else res -= n/t; //偶数个集合，系数为-1
        }
        System.out.println(res);
    }
}

博弈论

若一个游戏满足：
1，由两名玩家交替行动
2，在游戏进行的任意时刻，可以执行的合法行动与轮到哪位玩家无关
3，不能行动的玩家判负
则称该游戏为一个公平组合游戏

题目描述
给定n堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。

例如：有两堆石子，第一堆有2个，第二堆有3个，先手必胜。
操作步骤：

先手从第二堆拿走1个，此时第一堆和第二堆数目相同
无论后手怎么拿，先手都在另外一堆石子中取走相同数量的石子即可。

必胜状态 和 必胜状态

必胜状态：先手进行某一个操作，留给后手一个必败状态时，对于先手来说就是一个必胜状态。
即：先手可以走到某一个必败状态
必败状态：先手无论如何操作，留给后手都是一个必胜状态，对于先手来说是是一个必败状态。
即：先手走不到任何一个必败状态

结论： 假设n堆石子，石子数目分别是a1,a2,…,an，如果a1 ⊕ a2 ⊕…⊕ an≠0a1 ⊕ a2 ⊕…⊕ an≠0，先手必胜；否则先手必败。

证明：

操作到最后时，每堆石子数都是0 , 0⊕ 0...⊕ 0 = 0
在操作过程中，如果 a1 ⊕ a2 ... ⊕ an ≠ 0，那么玩家必然可以通过拿走某一堆石子将异或结果变为0
证明：不妨设x的二进制表示中最高一位1在第k位，那么在 a1,a2,…,an中，必然有一个数ai，它的第k为时1，且 ai ⊕ x < ai，那么从第i堆石子中拿走( ai − ai ⊕ x ) 个石子，第i堆石子还剩 ai - ( ai − ai ⊕ x ) = ai ⊕ x，此时 a1 ⊕ a2 ⊕ … ⊕ ai ⊕ x ⊕…⊕ an = x ⊕ x = 0。
在操作过程中，如果 a1 ⊕ a2 ⊕…⊕ an = 0，那么无论玩家怎么拿，必然会导致最终异或结果不为 0。

import java.util.Scanner;

public class Main{
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int ans = 0;
        while(n-- > 0){
            ans ^= sc.nextInt();
        }
        if(ans == 0) System.out.println("No");
        else System.out.println("Yes");
    }
}

最后编辑于：2021.06.17 23:44:16

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 202,802评论 5赞 476
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,109评论 2赞 379
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 149,683评论 0赞 335
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,458评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,452评论 5赞 364
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,505评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,901评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,550评论 0赞 256
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,763评论 1赞 296
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,556评论 2赞 319
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,629评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,330评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,898评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,897评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,140评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,807评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,339评论 2赞 342