基礎(chǔ)數(shù)論

素（質(zhì)）數(shù)

1）試除法判斷素?cái)?shù)

    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）分解質(zhì)因數(shù)

1)分解 n 的質(zhì)因數(shù)

   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 ! 的質(zhì)因數(shù)

 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;
    }

篩質(zhì)數(shù)

    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;
    }

篩區(qū)間[L ,R]之間的質(zhì)數(shù)
1）找出1-50000（sqrt(Integer.MAX)）之間的所有質(zhì)因子
2）對(duì)于1-50000中的每個(gè)質(zhì)數(shù) p 辟躏，將[L ,R]中所有p的倍數(shù)篩掉（至少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;
}

約（因）數(shù)

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）約數(shù)個(gè)數(shù)
n 個(gè)正整數(shù)乘積的約數(shù)個(gè)數(shù)
公式：
n=p1^a1 * p2^a2 * p3^a3 … pk^ak
約數(shù)個(gè)數(shù)：(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個(gè)2 , 可以選擇0 ~ cnt 個(gè) 2 
        }
        System.out.println(ans);
    }
}

3）約數(shù)之和
n個(gè)正整數(shù)的乘積的約數(shù)之和
公式：
n=p1^a1 * p2^a2 * p3^a3 … pk^ak
約數(shù)和：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個(gè)括號(hào)
             //從最內(nèi)層往外層算
            long t = 1;
            for(int i = 1 ; i <= a ; i++){
                t = (t*p+1) % mod;
            };
            res = res * t % mod;
        }
        System.out.println(res);
    }
}

4）最大公約數(shù)
歐幾里得算法（輾轉(zhuǎn)相除法）

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

4）最小公倍數(shù)
歐幾里得算法（輾轉(zhuǎn)相除法）

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

歐拉函數(shù)

1～N 中與 N 互質(zhì)的數(shù)的個(gè)數(shù)被稱(chēng)為歐拉函數(shù)雇盖，記為 ?(N)攒岛。
若在算數(shù)基本定理中， $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為質(zhì)數(shù)夜焦，則 φ(i) = n - 1 程梦，因?yàn)?1~ n-1中每個(gè)數(shù)都和 n 互質(zhì)
p為質(zhì)數(shù)，已知 φ(i) = i * x 粉捻，求 φ(p * i) ：
- 若 p 是 i 的約數(shù)，則 φ(p * i) = p * i * x = p * φ(i)
  因?yàn)?p 是 i 的約數(shù) 斑芜，所以在求 φ(i) 的公式中已經(jīng)乘了 (p - 1) / p 肩刃，雖然 p 也是 p * i 的約數(shù)，但在求某個(gè)數(shù)的歐拉函數(shù)的公式中杏头，只看約數(shù)盈包，而不看約數(shù)的次數(shù)。
- 若 p 不是 i 的約數(shù)醇王，則
  φ(i * p) = i * p * x * (p - 1) / p = i * x * (p - 1) = φ(i) * (p - 1)

1）求某個(gè)數(shù) 的歐拉函數(shù)

    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); //這里要先除 呢燥，因?yàn)椋╥-1）/ i 不能整除
            }
        }
        if(n > 1) res = res / n *(n - 1);
        return res;
    }

2）求 1 - n 之間的所有的數(shù)的歐拉函數(shù)之和

  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 為質(zhì)數(shù)，費(fèi)馬小定理 $b ^{p-1} \equiv 1 \pmod{p}$ 寓娩，即 $b * b^{p-2} \equiv 1 \pmod{p}$ 叛氨，所以 b 的逆元為 $b^{p-2} \pmod p$
b 不能為 p的倍數(shù) ，否則 $b^{p-2} \equiv 0 \pmod p$

    x = qmi(b,p-2,p) //調(diào)用上面求快速冪的函數(shù)即可

若 p 不是質(zhì)數(shù)棘伴，可以用擴(kuò)展歐幾里得算法求逆元：
a有逆元的充要條件是a與p互質(zhì)寞埠，所以gcd(a, p) = 1
假設(shè)a的逆元為x，那么有a * x ≡ 1 (mod p)
等價(jià)：ax + py = 1
exgcd(a, p, x, y)

擴(kuò)展歐幾里得

擴(kuò)展歐幾里得算法用于求解 ax + by = gcd(a , b)的解
當(dāng) b = 0 時(shí) , ax + by = a 焊夸，故 x = 1 , y = 0
當(dāng) b ≠ 0 時(shí) 仁连，
因?yàn)?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互質(zhì)時(shí) ， 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}$

擴(kuò)展歐幾里得可以求解 ax + by = gcd(a , b)
$a * x = b \pmod{m}$ ---> $a * x = b + k*m$ --> $a * x - m*k = b$
即 $a * x + my= b$

使用擴(kuò)展歐幾里得求得 $a * x_0 + m *y_0= gcd(a_ , m)$
1）裴蜀定理( Bezout )淳地，當(dāng) $b \% gcd(a , m) = 0$ 穗椅，原式有解额获，且 $\frac{x}{x_0} = \frac棍矛{gcd(a , m)}$ 你虹，故 $x = x_0 * \frac{gcd(a , m)} \% m$ ( % m 是要求 x 也在 1 - m直之間)
2）當(dāng) $b \% gcd(a , m) \neq 0$ 遣钳，原式無(wú)解

 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為正整數(shù)扰魂，且 a , n互質(zhì)
$a^{\phi(n)} = 1 \pmod{n}$

中國(guó)剩余定理

以?xún)蓚€(gè)式子 x = m1 (mod) a1 ，x = m2 (mod) a2開(kāi)始推導(dǎo)
$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}xihd83k并減去k \frac{a_2a_1}8ejwosr$ 蕴茴，得
$k_1 a_1 +k \frac{a_2a_1}urj07so - k_2 a_2 - k\frac{a_1 a_2}hn2y1ai = m_2 - m_1$
$(k_1 + k \frac{a_2}ntg1esy) a_1 - (k_2 + k \frac{a_1}vz5d8az) a_2 = m_2 - m_1$
即 $k_1 = k_1 + k\frac{a_2}vuorjiy 劝评，k_2 = k_2 + k \frac{a_1}asmnm0b$

則 $x = (k_1+ k\frac{a2}j7jfgp0 ) a_1 + m_1 ，即 x = k_1a_1 + m_1 + k\frac{a_1a_2}cztbtp7 ,其中 \frac{a_1 a_2}x3xefhm = a_1 ,a_2的最小公倍數(shù)$
$令 x_0 = k_1 a_1 +m_1 ,a= \frac{a_1 a_ 2}xio38sa倦淀，可得 x = x_0 + k a$
可以把 $x = x_0 + k a$ 繼續(xù)和后面的式子合并蒋畜，最后的形式就是一個(gè) $x = x_0 + k a$ 樣的式子
即答案 $x = x_0 \pmod{a} ，即x_0在1-a之間的余數(shù)$

注意的是：在每合并兩個(gè)式子的時(shí)候都需要判斷是否滿(mǎn)足 $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不知道正負(fù)
            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); //不知道正負(fù)姻成，所以取絕對(duì)值
        }
        if(!has_answer) System.out.println("-1");
        else System.out.println( (m1% a1 + a1) % a1 ); //取的是正數(shù)
    }
}

CRT.png

組合數(shù)

1）通過(guò)組合的思想求 $C_a^b = \frac{a!}{ (a-b)! b! } \pmod {1e^9 + 7}$
數(shù)據(jù)范圍特點(diǎn)：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}$
數(shù)據(jù)范圍特點(diǎn)：n比較大，a科展，b比較大均牢，對(duì) 1e9 + 7去模
1 ≤ n ≤ 10000,
1 ≤ b ≤ a ≤ 100000
主要過(guò)程是先預(yù)處理出 1-100000的階乘，階乘的逆元才睹，然后使用公式計(jì)算

    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 是質(zhì)數(shù)徘跪，費(fèi)馬小定理
        }
            
    }
//最后：
 ans =  fact[a] * infact[a - b] % mod  * infact[b] % mod

3）Lucas定理求 $C_a^b \pmod p$
數(shù)據(jù)范圍特點(diǎn)：n 很小，a , b非常大琅攘，p為質(zhì)數(shù)(比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$

當(dāng) a 或者 b 大于 p時(shí)垮庐，遞歸求解，當(dāng) a < p && b < p時(shí)乎澄，直接使用公式求解

    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）質(zhì)數(shù)線性篩法 + 高精度乘法求 $C_a^b$ 突硝，沒(méi)有取模
數(shù)據(jù)范圍特點(diǎn)：不對(duì)結(jié)果取模测摔，結(jié)果非常大
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）卡特蘭數(shù)
$f(n) = \frac{C_{2n}^n}{ n + 1 } ,$
變形： $f(n) = C_{2n}^n - C_{2n}^{n-1}$

滿(mǎn)足遞推式： f(n) = f(1) * f(n-1) + f(2) * f(n-2) + ....
有一種性質(zhì)：任意前綴中某種東西 >= 另外一種東西

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; //無(wú)解
            return 1;//無(wú)限解
        }
        //求解
        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;
        //從第一列開(kāi)始遍歷
        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的行和當(dāng)前行交換
            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個(gè)數(shù)
                                            // 對(duì)應(yīng)的為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的集合

置济，那么根據(jù)容斥原理，所有數(shù)的個(gè)數(shù)為各個(gè)集合的并集锋八，計(jì)算公式如下：

\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

實(shí)現(xiàn)思路
1）實(shí)際上并不需要知道每個(gè)集合里面的具體的元素是什么浙于，只需要知道集合的大小，大小為

| S_i| = n / p_i

挟纱。

2） $p_i$ 為質(zhì)數(shù)羞酗，這些數(shù)的乘積就是他們的最小公倍數(shù)，所以交集的大小就是 n除以它們的乘積紊服，交集的大小為 $S_1 \bigcap S_2 = n / (p_1 * p_2)$

3）使用二進(jìn)制作為集合狀態(tài)的表示檀轨，比如有 4 個(gè)質(zhì)數(shù)， m = 4欺嗤，所以需要 4 位二進(jìn)制進(jìn)行表示参萄，每個(gè)二進(jìn)制位表示集合 $S_i$ 是否被選中，例如： $\begin{matrix} m=4 \\ \overbrace{ 1101 }\end{matrix}$ 煎饼，表示的集合 $S_1 , S_2 , S_4$ 被選中讹挎，這個(gè)集合的元素個(gè)數(shù)為 $n / (p_1 * p _2 * p _4)$ ，在公式中吆玖，系數(shù)為 $(-1)^{k-1}$ 筒溃，k為選中的集合個(gè)數(shù) ，即選中奇數(shù)個(gè)集合前面的系數(shù)為1沾乘，偶數(shù)個(gè)集合系數(shù)為 -1怜奖。

實(shí)現(xiàn)代碼：

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個(gè)1)的每一個(gè)集合狀態(tài)，（至少選中一個(gè)集合） 
        for(int i = 1 ; i < 1 << m ; i ++){  //
            int t = 1; //選中的集合對(duì)應(yīng)的乘積
            int s = 0;//選中的集合數(shù)量
            
            //枚舉當(dāng)前狀態(tài)的每一位
            for(int j = 0; j < m ; j ++){
                //第j個(gè)集合被選中了
                if( (( i>>j ) & 1 ) == 1 ){
                    //乘積大于n , 則 n/t = 0 翅阵，跳出這輪循環(huán)
                    if( (long) t * p[j] > n ){
                        t = -1;
                        break;
                    }
                    s++;
                    t *= p[j];
                }    
            }
    
            if(t == -1) continue;
            
            if( (s&1) == 1 ) res += n/t; //選中奇數(shù)個(gè)集合歪玲，系數(shù)為1
            else res -= n/t; //偶數(shù)個(gè)集合尽爆，系數(shù)為-1
        }
        System.out.println(res);
    }
}

博弈論

若一個(gè)游戲滿(mǎn)足：
?1，由兩名玩家交替行動(dòng)
?2读慎，在游戲進(jìn)行的任意時(shí)刻漱贱，可以執(zhí)行的合法行動(dòng)與輪到哪位玩家無(wú)關(guān)
?3，不能行動(dòng)的玩家判負(fù)
則稱(chēng)該游戲?yàn)橐粋€(gè)公平組合游戲

題目描述
給定n堆石子夭委，兩位玩家輪流操作幅狮，每次操作可以從任意一堆石子中拿走任意數(shù)量的石子（可以拿完，但不能不拿）株灸，最后無(wú)法進(jìn)行操作的人視為失敗崇摄。
問(wèn)如果兩人都采用最優(yōu)策略，先手是否必勝慌烧。

例如：有兩堆石子逐抑，第一堆有2個(gè)，第二堆有3個(gè)屹蚊，先手必勝厕氨。
操作步驟：

先手從第二堆拿走1個(gè)，此時(shí)第一堆和第二堆數(shù)目相同
無(wú)論后手怎么拿汹粤，先手都在另外一堆石子中取走相同數(shù)量的石子即可命斧。

必勝狀態(tài) 和 必勝狀態(tài)

必勝狀態(tài)：先手進(jìn)行某一個(gè)操作，留給后手一個(gè)必?cái)顟B(tài)時(shí)嘱兼，對(duì)于先手來(lái)說(shuō)就是一個(gè)必勝狀態(tài)国葬。
即：先手可以走到某一個(gè)必?cái)顟B(tài)
必?cái)顟B(tài)：先手無(wú)論如何操作，留給后手都是一個(gè)必勝狀態(tài)芹壕，對(duì)于先手來(lái)說(shuō)是是一個(gè)必?cái)顟B(tài)汇四。
即：先手走不到任何一個(gè)必?cái)顟B(tài)

結(jié)論： 假設(shè)n堆石子，石子數(shù)目分別是a1,a2,…,an踢涌，如果a1 ⊕ a2 ⊕…⊕ an≠0a1 ⊕ a2 ⊕…⊕ an≠0通孽，先手必勝；否則先手必?cái)　?/p>

證明：

操作到最后時(shí)斯嚎，每堆石子數(shù)都是0 , 0⊕ 0...⊕ 0 = 0
在操作過(guò)程中利虫，如果 a1 ⊕ a2 ... ⊕ an ≠ 0，那么玩家必然可以通過(guò)拿走某一堆石子將異或結(jié)果變?yōu)?
證明：不妨設(shè)x的二進(jìn)制表示中最高一位1在第k位堡僻，那么在 a1,a2,…,an中糠惫，必然有一個(gè)數(shù)ai，它的第k為時(shí)1钉疫，且 ai ⊕ x < ai硼讽，那么從第i堆石子中拿走( ai ? ai ⊕ x ) 個(gè)石子，第i堆石子還剩 ai - ( ai ? ai ⊕ x ) = ai ⊕ x牲阁，此時(shí) a1 ⊕ a2 ⊕ … ⊕ ai ⊕ x ⊕…⊕ an = x ⊕ x = 0固阁。
在操作過(guò)程中壤躲，如果 a1 ⊕ a2 ⊕…⊕ an = 0，那么無(wú)論玩家怎么拿备燃，必然會(huì)導(dǎo)致最終異或結(jié)果不為 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

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市并齐，隨后出現(xiàn)的幾起案子漏麦，更是在濱河造成了極大的恐慌，老刑警劉巖况褪，帶你破解...
沈念sama閱讀 206,482評(píng)論 6贊 481
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件撕贞，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡测垛，警方通過(guò)查閱死者的電腦和手機(jī)捏膨，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,377評(píng)論 2贊 382
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)食侮，“玉大人号涯，你說(shuō)我怎么就攤上這事「砻瑁” “怎么了诚隙？”我有些...
開(kāi)封第一講書(shū)人閱讀 152,762評(píng)論 0贊 342
道士緝兇錄：失蹤的賣(mài)姜人
文/不壞的土叔我叫張陵讶隐，是天一觀的道長(zhǎng)起胰。經(jīng)常有香客問(wèn)我，道長(zhǎng)巫延，這世上最難降的妖魔是什么效五？我笑而不...
開(kāi)封第一講書(shū)人閱讀 55,273評(píng)論 1贊 279
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮炉峰，結(jié)果婚禮上畏妖，老公的妹妹穿的比我還像新娘。我一直安慰自己疼阔，他們只是感情好戒劫，可當(dāng)我...
茶點(diǎn)故事閱讀 64,289評(píng)論 5贊 373
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布。她就那樣靜靜地躺著婆廊，像睡著了一般迅细。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上淘邻，一...
開(kāi)封第一講書(shū)人閱讀 49,046評(píng)論 1贊 285
城市分裂傳說(shuō)
那天茵典，我揣著相機(jī)與錄音，去河邊找鬼宾舅。笑死统阿，一個(gè)胖子當(dāng)著我的面吹牛彩倚，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播扶平，決...
沈念sama閱讀 38,351評(píng)論 3贊 400
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼帆离，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來(lái)了结澄？” 一聲冷哼從身側(cè)響起盯质，我...
開(kāi)封第一講書(shū)人閱讀 36,988評(píng)論 0贊 259
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎概而，沒(méi)想到半個(gè)月后呼巷，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 43,476評(píng)論 1贊 300
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡赎瑰，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 35,948評(píng)論 2贊 324
?白月光啟示錄
正文我和宋清朗相戀三年王悍，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片餐曼。...
茶點(diǎn)故事閱讀 38,064評(píng)論 1贊 333
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡压储，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出源譬，到底是詐尸還是另有隱情集惋，我是刑警寧澤，帶...
沈念sama閱讀 33,712評(píng)論 4贊 323
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布踩娘，位于F島的核電站刮刑，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏养渴。R本人自食惡果不足惜雷绢，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,261評(píng)論 3贊 307
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望理卑。院中可真熱鬧翘紊，春花似錦、人聲如沸藐唠。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 30,264評(píng)論 0贊 19
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)宇立。三九已至踪宠，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間泄伪，已是汗流浹背殴蓬。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 31,486評(píng)論 1贊 262
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人染厅。一個(gè)月前我還...
沈念sama閱讀 45,511評(píng)論 2贊 354
代替公主和親
正文我出身青樓痘绎，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親肖粮。傳聞我的和親對(duì)象是個(gè)殘疾皇子孤页，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 42,802評(píng)論 2贊 345