分解质因数

import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 200010;
        static final int inf = 0x3f3f3f3f;

        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int T;
            T = sc.nextInt();

            while(T -- > 0)
            {
                int n = sc.nextInt();

                for(int i = 2; i <= n / i; i ++)
                {
                    int cnt = 0;
                    if(n % i == 0)
                    {
                        while(n % i == 0) 
                        {
                            cnt ++;
                            n /= i;
                        }

                        System.out.printf("%d %d\n", i, cnt);
                    }

                }

                if(n > 1) System.out.printf("%d %d\n", n, 1);

                System.out.println();
            }
        }     
}

筛质数

(1) 埃氏筛法

import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 1000010;
        static final int inf = 0x3f3f3f3f;
        static boolean[] vis = new boolean[N]; //标记数组
        static int[] primes = new int[N];  //存质数的数组
        static int cnt, n;

        public static void get_prime()
        {
            for(int i = 2; i <= n; i ++)
            {
                if(!vis[i]) 
                {
                    primes[cnt ++] = i;

                    for(int j = 2 * i; j <= n; j += i) vis[j] = true;
                }
            }
        }

        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            n = sc.nextInt();

            get_prime();

            System.out.println(cnt);
        }     
}

(2)线性筛

import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 1000010;
        static final int inf = 0x3f3f3f3f;
        static boolean[] vis = new boolean[N]; //标记数组
        static int[] primes = new int[N];  //存质数的数组
        static int cnt, n;

        public static void get_prime() //时间复杂度为O(n)
        {
            for(int i = 2; i <= n; i ++)
            {
                if(!vis[i]) primes[cnt ++] = i;

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

        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            n = sc.nextInt();

            get_prime();

            System.out.println(cnt);
        }     
}

试除法求约数

import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 1000010;
        static final int inf = 0x3f3f3f3f;
        static int[] ans = new int[N];  //存约数的数组
        static int cnt, n;

        public static void divide(int x)
        {
            for(int i = 1; i <= x / i; i ++)
            {
                if(x % i == 0) 
                {
                    ans[cnt ++] = i;
                    if(x / i != i) ans[cnt ++] = x / i;
                }
            }
        }

        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int T  = sc.nextInt();

            while(T -- > 0)
            {
                n = sc.nextInt();
                cnt = 0;
                divide(n);

                Arrays.sort(ans, 0, cnt);

                for(int i = 0; i < cnt; i ++) System.out.printf("%d ", ans[i]);
                System.out.println();
            }
        }     
}

约数个数

// 基本思想 
    //如果 N = p1^c1 * p2^c2 * ... *pk^ck
    //约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
import java.util.*;
public class Main{
    static int mod = (int)1e9 + 7;
    public static void main(String[] args){
        Map<Integer,Integer> map = new HashMap<>(); //创建一个哈希表
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        while(n -- > 0){
            int x = scan.nextInt();
            //下面这里是运用了分解质因数的模板，
            for(int i = 2 ; i <= x / i ; i ++ ){
                while(x % i == 0){
                    x /= i;
                    // map.getOrDefault(i,0) 这个是获取对应i位置的values值
                    map.put(i,map.getOrDefault(i,0) + 1); 
                }
            }
            if(x > 1) map.put(x,map.getOrDefault(x,0)  + 1 );
        }

        long res = 1;
        //map.keySet()获取所有的key值,map.values()获取所有的values值，两种方法都可以
        for(int key : map.values()){
            res = res * (key + 1) % mod;
        }
        System.out.println(res);
    }
}

约数之和

import java.util.*;
public class Main{
    static int mod = (int)1e9 + 7;
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        Map<Integer,Integer> map = new HashMap<>();
        int n = scan.nextInt();
        while(n -- > 0){
            int x  = scan.nextInt();
            for(int i = 2 ; i <= x / i ; i ++ ){
                while(x % i == 0){
                    x /= i;
                    map.put(i,map.getOrDefault(i,0) + 1);
                }
            }
            if(x > 1) map.put(x,map.getOrDefault(x,0) + 1);
        }
        long res = 1;
        for(int a : map.keySet()){
            //int a = map.getKey();
            int b = map.get(a);
            long t = 1; 
            //这里为什么是t * a + 1,后面的一是我们将没有将t等于0，所以我们自己将a的0次方写成1，方便代码表达
            while(b -- > 0) t = (t * a + 1) % mod;
            //求约数之和就是分解质因数之后，将每一个质因数的质数从0到最大进行罗列相加，最后所有质数的罗列相乘
           // p = a ^ 3 * b ^ 1;
           // sum = (a ^ 0 + a ^ 1 + a ^ 2 + a ^ 3) * (b ^ 0 + b ^ 1)
           // 这个结果就是我们想要求得约数之和
            res = res * t % mod;
        }
        System.out.println(res);
    }
}

最大公约数gcd

求最小公倍数lcm多一步即可，lcm(a, b) = a * b / gcd(a, b)

import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 1000010;
        static final int MOD = (int)1e9 + 7;


        public static int gcd(int x, int y)
        {
            if(y == 0) return x;
            else return gcd(y, x % y);
        }
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int T  = sc.nextInt();

            while(T -- > 0)
            {
                int a, b;
                a = sc.nextInt();
                b = sc.nextInt();
                System.out.println(gcd(a, b));
            }

        }     
}

快速幂

import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 1000010;
        static final int MOD = (int)1e9 + 7;

        public static long qmi(long a, long b, long p)
        {
            long res = 1;
            while(b > 0)
            {
                if((b & 1) == 1)
                {
                    res = res * a % p;
                }
                a = a * a % p;
                b >>= 1;
            }
            return res;
        }
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int T  = sc.nextInt();

            while(T -- > 0)
            {
                long a = sc.nextLong();
                long b = sc.nextLong();
                long p = sc.nextLong();

                System.out.println(qmi(a, b, p));
            }

        }     
}

求欧拉函数

package test;
import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 110, p = 131;
        static final long Q = Long.MAX_VALUE;

        public static void main(String[] args) throws Exception {
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int n = sc.nextInt();
            while(n -- > 0)
            {
                int x = sc.nextInt();

                int res = x;
                for(int i = 2; i <= x / i; i ++)
                {
                    if(x % i == 0)
                    {
                        while(x % i == 0) x /= i;
                        res = res / i * (i - 1);  //先乘后除，防止answer出错
                    }

                }
                if(x > 1) res = res / x * (x - 1);
                System.out.println(res);
            }
}
}

两个互质的数p，q，最大不能够凑出来的数为（p - 1）* （q - 1） - 1

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1010;
int p, q;
//两个互质的数p，q，最大不能够凑出来的数为（p - 1）* （q - 1） - 1 
int main()
{
    ios::sync_with_stdio(false);
    cin >> p >> q;
    cout << (p - 1) * (q - 1) - 1 << endl;  
    return 0;
}

快速幂求逆元

import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 200010, B = N / 2; //b为设置的偏移量 
        static boolean[][] dp = new boolean[101][N];
        static int n;

        public static long qmi(long a, long b, long p)
        {
            long res = 1;
            while(b > 0)
            {
                if((b & 1) == 1)
                {
                    res = res * a % p;
                }
                a = a * a % p;
                b >>= 1;
            }

            return res;
        }
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            n = sc.nextInt();
            for(int i = 1; i <= n; i ++)
            {
                long a = sc.nextLong();
                long p = sc.nextLong();
                if(a % p == 0) System.out.println("impossible");
                else System.out.println(qmi(a, p - 2, p));
            }
       }   
}

组合数

递推方式求组合数

import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 2010, MOD = (int)1e9 + 7; //b为设置的偏移量 
        static int[][] C = new int[N][N];


        public static void init()
        {
            for(int i = 0; i < N; i ++)
                for(int j = 0; j <= i; j ++)
                {
                    if(j == 0) C[i][j] = 1;
                    else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
                }
        }
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

            int n;
            n = sc.nextInt();
            init();
            for(int i = 1; i <= n; i ++)
            {
                int a = sc.nextInt();
                int b = sc.nextInt();
                System.out.println(C[a][b]);
            }
       }   
}

利用逆元求组合数

import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 100010, MOD = (int)1e9 + 7; //b为设置的偏移量 
        static long[] fac = new long[N];

        public static void init()
        {
            fac[0] = 1;
            for(int i = 1; i < N; i ++)
            {
                fac[i] = (fac[i - 1] * i) % MOD;
            }
        }

        public static long qmi(long a, long b)
        {
            long res = 1;
            while(b > 0)
            {
                if((b & 1) == 1)
                {
                    res = res * a % MOD;
                }
                a = a * a % MOD;
                b >>= 1;
            }
            return res;
        }


        public static long inv(long x) //求逆元的函数
        {
            return qmi(x, MOD - 2);
        }


        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            init();
            int n = sc.nextInt();

            for(int i = 1; i <= n; i ++)
            {
                int a = sc.nextInt();
                int b = sc.nextInt();

                long ans = (fac[a] * inv(fac[b]) % MOD * inv(fac[a - b]) % MOD);
                System.out.println(ans);
            }
       }   
}

卡特兰数递推式

解决问题：
（1）有 2n 个人排成一行进入剧场。入场费 5 元。其中只有 n 个人有一张 5 元钞票，另外 n 人只有 10 元钞票，剧院无其它钞票，问有多少种方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？
卡特兰数

#include <iostream>
using namespace std;
int n;
long long f[25];

int main() {
  f[0] = 1;
  cin >> n;
  for (int i = 1; i <= n; i++) f[i] = f[i - 1] * (4 * i - 2) / (i + 1);
  // 这里用的是常见公式2
  cout << f[n] << endl;
  return 0;
}

错排问题

n封不同的信与n个不同的信封,求将n封信都装错信封的方案个数 ;
公式详解

递推公式

D(n) = (n−1) * (D(n−1) + D(n−2))

#include<iostream>
using namespace std;

int fun(int n)
{
    //边界情况的嘞
    if(n==1)
        return 0;
    if(n==2)
        return 1;
    return (n-1)*(fun(n-1)+fun(n-2));
}
int main()
{
    int n;
    cin>>n;
    cout<<fun(n);
    return 0;
}