数学

筛质数

• 埃式筛

const int N=10001;
int primes[N],cnt=0;
bool st[N];
void get_p(int n){
    for(int i=2;i<=n;i++){
        if(!st[i])primes[cnt++]=i;
        for(int j=i+i;j<=n;j+=i){
                st[j]=true;
        }

    }
}

• 线性筛

const int N=10001;
int primes[N],cnt=0;
bool st[N];
void get_prime(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;
        }
    }
}

费马逆元

import java.util.*;

public class Main {
    static long MOD = (long)1e9 + 7;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int q = sc.nextInt();
        int maxN = 0;
        int[] nList = new int[q];
        int[] mList = new int[q];

        // 读取所有查询并找到最大的 n
        for (int i = 0; i < q; i++) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            nList[i] = n;
            mList[i] = m;
            if (n > maxN) {
                maxN = n;
            }
        }

        // 预处理阶乘和逆元
        long[] factorial = new long[maxN + 1];
        long[] inverse = new long[maxN + 1];
        factorial[0] = 1;
        for (int i = 1; i <= maxN; i++) {
            factorial[i] = (factorial[i - 1] * i) % MOD;
        }

        // 使用费马小定理计算逆元
        inverse[maxN] = fastPower(factorial[maxN], MOD - 2, MOD);
        for (int i = maxN - 1; i >= 0; i--) {
            inverse[i] = (inverse[i + 1] * (i + 1)) % MOD;
        }

        // 处理每个查询
        for (int i = 0; i < q; i++) {
            int n = nList[i];
            int m = mList[i];
            if (m < 0  m > n) {
                System.out.println(0);
                continue;
            }
            long ans = (factorial[n] * inverse[m] % MOD) * inverse[n - m] % MOD;
            System.out.println(ans);
        }

        sc.close();
    }

    // 快速幂算法
    public static long fastPower(long base, long exponent, long mod) {
        long result = 1;
        base %= mod;
        while (exponent > 0) {
            if ((exponent & 1) == 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exponent >>= 1;
        }
        return result;
    }
}

快速幂

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();

        // 测试用例 1: 正指数
        double result1 = solution.myPow(2.0, 10);
        System.out.println("2^10 = " + result1); // 输出: 1024.0

        // 测试用例 2: 负指数
        double result2 = solution.myPow(2.0, -2);
        System.out.println("2^-2 = " + result2); // 输出: 0.25

        // 测试用例 3: 零指数
        double result3 = solution.myPow(5.0, 0);
        System.out.println("5^0 = " + result3); // 输出: 1.0

        // 测试用例 4: 边界条件 (0^0)
        double result4 = solution.myPow(0.0, 0);
        System.out.println("0^0 = " + result4); // 输出: 1.0

        // 测试用例 5: 整数溢出测试 (Integer.MIN_VALUE)
        double result5 = solution.myPow(2.0, Integer.MIN_VALUE);
        System.out.println("2^" + Integer.MIN_VALUE + " = " + result5); // 输出一个非常小的数
    }
}

class Solution {
    public double myPow(double x, int n) {
        long N = n; // 将指数转换为 long 类型以避免溢出
        if (N < 0) {
            x = 1 / x; // 处理负指数
            N = -N;    // 将指数转为正数
        }
        return powIterative(x, N);
    }

    // 迭代实现快速幂
    private double powIterative(double x, long n) {
        double result = 1.0; // 初始化结果
        while (n > 0) {
            if (n % 2 == 1) { // 如果指数是奇数
                result *= x;  // 将当前的 x 乘到结果中
            }
            x *= x; // 平方 x
            n /= 2; // 将指数减半
        }
        return result;
    }
}

欧几里得和欧拉

import java.util.Scanner;

public class Main{
    static int mod=9901; // 定义模数，用于结果取模
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        int A=scan.nextInt(),B=scan.nextInt(); // 输入A和B
        int res=1; // 初始化结果为1，用于累积各质因数等比和的乘积
        
        // 质因数分解A，从2开始试除
        for(int i=2;i*i<=A;i++){
            if(A%i==0){
                int s=0; // 记录当前质因数i的指数
                while(A%i==0){
                    A/=i; // 除去所有i因子
                    s++;
                }
                // 计算i^(s*B)的等比和，并累积到结果中
                res=res*sum(i,s*B+1)%mod; // s*B+1项（0次方到s*B次方）
            }
        }
        // 处理剩余的质因数（当A是质数时）
        if(A>1)res=res*sum(A,B+1)%mod; // 指数为1*B，项数为B+1
        if(A==0)res=0; // 特判A=0的情况，结果直接为0
        System.out.println(res);
    }
    
    // 快速幂算法：计算a^k % mod
    public static int quic(int a,int k){
        int res=1;
        a%=mod; // 先取模，防止溢出
        while(k>0){
            if((k&1)==1){ // 如果当前二进制位为1，乘入结果
                res=(res*a)%mod;
            }
            a=(a*a)%mod; // a自乘，相当于计算下一位的权值
            k>>=1; // 右移一位，处理下一位二进制
        }
        return res;
    }
    
    // 分治法计算等比数列和：1 + p + p^2 + ... + p^(k-1)
    public static int sum(int p,int k){
        if(k==1)return 1; // 边界条件，只有1项
        if(k%2==0){ // 当k为偶数时，拆分成两部分
            // sum(p,k) = (1 + p^(k/2)) * sum(p, k/2)
            return ((1+quic(p,k/2))*sum(p,k/2))%mod;
        } else { // 当k为奇数时，拆分为前k-1项和最后一项
            // sum(p,k) = sum(p,k-1) + p^(k-1)
            return (sum(p,k-1)+quic(p,k-1))%mod;
        }
    }
}