Lucas定理和费马小定理在竞赛中的应用

本文详细介绍Lucas定理和费马小定理的数学原理及其在算法竞赛中的应用，并提供Java代码实现和实际竞赛例题分析。

一、数学原理介绍

1.1 费马小定理(Fermat’s Little Theorem)

费马小定理是数论中的一个重要定理，由法国数学家皮埃尔·德·费马提出。

定理内容：如果p是质数，a是整数且不是p的倍数，则有：

a^(p-1) ≡ 1 (mod p)

等价形式：对于任意整数a和质数p，有：

a^p ≡ a (mod p)

证明思路：

• 考虑集合S = {1, 2, …, p-1}
• 将S中每个元素乘以a（模p），得到集合T = {a·1 mod p, a·2 mod p, …, a·(p-1) mod p}
• 可以证明T中的元素互不相同且都不为0
• 因此T是S的一个排列
• 两个集合的元素乘积相等：(a·1)·(a·2)·…·(a·(p-1)) ≡ 1·2·…·(p-1) (mod p)
• 整理得：a^(p-1)·(p-1)! ≡ (p-1)! (mod p)
• 由于(p-1)!与p互质，可以消去，得到a^(p-1) ≡ 1 (mod p)

1.2 Lucas定理(Lucas’ Theorem)

Lucas定理用于在模质数p的情况下计算组合数。

定理内容：对于非负整数n和m，以及质数p，有：

C(n, m) ≡ C(n0, m0) × C(n1, m1) × ... × C(nk, mk) (mod p)

其中，n = n0 + n1·p + n2·p² + … + nk·p^k，m = m0 + m1·p + m2·p² + … + mk·p^k，是n和m的p进制表示。

简化理解：

• 将n和m表示为p进制
• 分别计算每一位上的组合数
• 将这些组合数相乘，结果即为C(n,m) mod p

二、竞赛中的应用场景

2.1 费马小定理的应用

1. 模运算下的除法：

   • 在模p下，a/b可以表示为a·b^(-1) mod p
   • 利用费马小定理，b^(-1) ≡ b^(p-2) (mod p)
   • 因此a/b ≡ a·b^(p-2) (mod p)

2. 快速幂取模：

   • 计算a^b mod p时，可以利用费马小定理降低指数
   • 当b很大时，可以用b mod (p-1)替代b

3. 逆元计算：

   • 在模p下，a的乘法逆元是a^(p-2)
   • 用于解决除法取模问题

2.2 Lucas定理的应用

1. 大组合数取模：

   • 当n和m非常大时，直接计算C(n,m)会溢出
   • 使用Lucas定理可以将大组合数分解为小组合数的乘积

2. 组合数取模质数幂：

   • 扩展Lucas定理可以处理模质数幂的情况

3. 数位DP问题：

   • 在某些数位DP问题中，需要计算组合数取模

三、Java代码实现

3.1 费马小定理实现

public class FermatTheorem {
    // 计算 (a^b) % mod
    public static long fastPow(long a, long b, long mod) {
        long result = 1;
        a %= mod;
        while (b > 0) {
            if ((b & 1) == 1) {
                result = (result * a) % mod;
            }
            a = (a * a) % mod;
            b >>= 1;
        }
        return result;
    }
    
    // 使用费马小定理计算乘法逆元
    public static long modInverse(long a, long mod) {
        if (gcd(a, mod) != 1) {
            throw new ArithmeticException("Modular inverse does not exist");
        }
        return fastPow(a, mod - 2, mod);
    }
    
    // 计算最大公约数
    private static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    // 使用费马小定理计算模p下的除法
    public static long modDivide(long a, long b, long mod) {
        return (a * modInverse(b, mod)) % mod;
    }
}

3.2 Lucas定理实现

public class LucasTheorem {
    // 计算组合数 C(n,m)
    public static long combination(long n, long m, long mod) {
        if (m > n) return 0;
        if (m > n - m) m = n - m;
        
        long numerator = 1;
        long denominator = 1;
        
        for (int i = 0; i < m; i++) {
            numerator = (numerator * (n - i)) % mod;
            denominator = (denominator * (i + 1)) % mod;
        }
        
        return FermatTheorem.modDivide(numerator, denominator, mod);
    }
    
    // Lucas定理实现
    public static long lucas(long n, long m, long p) {
        if (m == 0) return 1;
        return (combination(n % p, m % p, p) * 
                lucas(n / p, m / p, p)) % p;
    }
}

3.3 扩展Lucas定理（处理质数幂）

public class ExtendedLucas {
    // 扩展欧几里得算法
    private static long[] exgcd(long a, long b) {
        if (b == 0) {
            return new long[]{1, 0, a};
        }
        long[] result = exgcd(b, a % b);
        long x = result[0];
        long y = result[1];
        result[0] = y;
        result[1] = x - (a / b) * y;
        return result;
    }
    
    // 计算乘法逆元（不使用费马小定理）
    private static long modInverse(long a, long mod) {
        long[] result = exgcd(a, mod);
        return (result[0] % mod + mod) % mod;
    }
    
    // 计算n!中因子p的个数
    private static long factorialPrimePower(long n, long p) {
        long count = 0;
        while (n > 0) {
            n /= p;
            count += n;
        }
        return count;
    }
    
    // 计算n! mod p^k，其中p^k不整除n!
    private static long factorialModPrimePower(long n, long p, long pk) {
        long result = 1;
        for (long i = 1; i <= n; i++) {
            if (i % p != 0) {
                result = (result * i) % pk;
            }
        }
        
        // 计算循环节
        if (n >= pk) {
            result = (result * factorialModPrimePower(n / pk, p, pk)) % pk;
        }
        
        return result;
    }
    
    // 计算组合数C(n,m) mod p^k
    public static long combinationModPrimePower(long n, long m, long p, long k) {
        long pk = (long) Math.pow(p, k);
        
        // 计算n!、m!和(n-m)!中p的幂次
        long pn = factorialPrimePower(n, p);
        long pm = factorialPrimePower(m, p);
        long pnm = factorialPrimePower(n - m, p);
        
        // 如果p的幂次不够，返回0
        if (pn > pm + pnm) {
            return 0;
        }
        
        // 计算不包含p因子的部分
        long numerator = factorialModPrimePower(n, p, pk);
        long denominator = (factorialModPrimePower(m, p, pk) * 
                           factorialModPrimePower(n - m, p, pk)) % pk;
        
        return (numerator * modInverse(denominator, pk)) % pk;
    }
    
    // 中国剩余定理合并结果
    public static long chineseRemainderTheorem(long[] remainders, long[] moduli) {
        long product = 1;
        for (long mod : moduli) {
            product *= mod;
        }
        
        long result = 0;
        for (int i = 0; i < remainders.length; i++) {
            long m = product / moduli[i];
            long inverse = modInverse(m, moduli[i]);
            result = (result + remainders[i] * m * inverse) % product;
        }
        
        return result;
    }
    
    // 扩展Lucas定理
    public static long extendedLucas(long n, long m, long p, long k) {
        // 对于质数幂p^k，使用组合数模质数幂的方法
        return combinationModPrimePower(n, m, p, k);
    }
}

四、竞赛例题分析

例题1：大组合数取模（基础应用）

题目描述：
计算C(n,m) mod p，其中n和m可能非常大（n,m ≤ 10^18），p是质数（p ≤ 10^5）。

分析：

• 直接计算C(n,m)会溢出
• 使用Lucas定理可以解决

Java实现：

import java.util.Scanner;

public class LargeCombinatorialNumber {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        long m = scanner.nextLong();
        long p = scanner.nextLong();
        
        System.out.println(LucasTheorem.lucas(n, m, p));
    }
}

例题2：模运算下的除法（费马小定理应用）

题目描述：
给定n个正整数a₁, a₂, …, aₙ和质数p，计算(a₁ × a₂ × … × aₙ)⁻¹ mod p。

分析：

• 需要计算乘积的模逆元
• 使用费马小定理计算每个数的逆元，然后相乘

Java实现：

import java.util.Scanner;

public class ModularInverseProduct {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long p = scanner.nextLong();
        
        long result = 1;
        for (int i = 0; i < n; i++) {
            long a = scanner.nextLong();
            // 计算a的逆元
            long inverse = FermatTheorem.modInverse(a, p);
            result = (result * inverse) % p;
        }
        
        System.out.println(result);
    }
}

例题3：组合数取模质数幂（扩展Lucas定理应用）

题目描述：
计算C(n,m) mod p^k，其中n,m ≤ 10^6，p是质数，k ≤ 10。

分析：

• 基本Lucas定理只适用于模质数的情况
• 需要使用扩展Lucas定理处理模质数幂的情况

Java实现：

import java.util.Scanner;

public class CombinationModPrimePower {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        long m = scanner.nextLong();
        long p = scanner.nextLong();
        long k = scanner.nextLong();
        
        System.out.println(ExtendedLucas.extendedLucas(n, m, p, k));
    }
}

例题4：快速幂与费马小定理结合（优化大指数）

题目描述：
计算a^b mod p，其中a,b,p ≤ 10^18，p是质数。

分析：

• 直接使用快速幂计算a^b mod p，当b非常大时效率低下
• 根据费马小定理，a^(p-1) ≡ 1 (mod p)
• 因此a^b ≡ a^(b mod (p-1)) (mod p)，当b ≥ p-1时
• 特别地，当b < p-1时，直接计算a^b mod p

Java实现：

import java.util.Scanner;

public class LargeExponentiation {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long a = scanner.nextLong();
        long b = scanner.nextLong();
        long p = scanner.nextLong();
        
        // 处理特殊情况
        if (p == 1) {
            System.out.println(0);
            return;
        }
        
        // 处理a是p的倍数的情况
        if (a % p == 0) {
            System.out.println(0);
            return;
        }
        
        // 应用费马小定理优化
        if (b >= p - 1) {
            b = b % (p - 1);
            // 特殊情况：b变为0，实际上是p-1
            if (b == 0) {
                b = p - 1;
            }
        }
        
        System.out.println(FermatTheorem.fastPow(a, b, p));
    }
}

例题5：组合数学问题（Lucas定理实际应用）

题目描述：
有n个不同的球和m个不同的盒子，每个盒子可以放任意数量的球，求不同的放置方法数量，对10^9+7取模。

分析：

• 这是一个经典的组合数学问题，等价于将n个球放入m个盒子，每个盒子至少放一个球
• 答案为C(n-1, m-1)，即从n-1个位置中选择m-1个隔板的方法数
• 当n和m很大时，需要使用Lucas定理计算

Java实现：

import java.util.Scanner;

public class BallsAndBoxes {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        long m = scanner.nextLong();
        long mod = 1000000007; // 10^9 + 7
        
        // 特殊情况处理
        if (m > n) {
            System.out.println(0); // 盒子比球多，不可能每个盒子至少一个球
            return;
        }
        
        // 计算C(n-1, m-1) mod (10^9 + 7)
        // 由于10^9 + 7是质数，可以直接使用Lucas定理
        System.out.println(LucasTheorem.combination(n - 1, m - 1, mod));
    }
}

五、总结与拓展

5.1 两个定理的联系

费马小定理和Lucas定理在竞赛中经常结合使用：

• 费马小定理用于计算模质数情况下的乘法逆元
• Lucas定理利用这些逆元计算大组合数取模

5.2 实际应用技巧

1. 预处理优化：

   • 对于多次查询的情况，可以预处理阶乘及其逆元
   • 时间复杂度从O(n)降至O(1)查询

2. 模数分解：

   • 当模数不是质数时，可以分解为质数幂的乘积
   • 使用中国剩余定理合并结果

3. 数值溢出处理：

   • 使用long类型或BigInteger处理大数
   • 中间计算过程及时取模

5.3 相关拓展

1. Wilson定理：对于质数p，有(p-1)! ≡ -1 (mod p)

2. 欧拉定理：费马小定理的推广，若gcd(a,n)=1，则a^φ(n) ≡ 1 (mod n)，其中φ(n)为欧拉函数

3. 扩展Lucas定理：处理模数为质数幂或合数的情况

在算法竞赛中，熟练掌握这些数论工具可以有效解决各种组合数学和模运算问题，是提高竞赛水平的重要一环。