3. 卢卡斯定理

887. 求组合数 III
给定 n 组询问，每组询问给定三个整数 a,b,p，其中 p 是质数，请你输出的值。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一组 a,b,p。
输出格式
共 n 行，每行输出一个询问的解。
数据范围
1≤n≤20
1≤b≤a≤1018,
1≤p≤105,
输入样例：

3
5 3 7
3 1 5
6 4 13

输出样例：

3
3
2

要素

• 1≤n≤20
• 1≤b≤a≤1018,
• 1≤p≤105,

卢卡斯定理

卢卡斯定理.pdf

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        while (m-- > 0) {
            long a = sc.nextLong(), b = sc.nextLong();
            int p = sc.nextInt();
            int res = lucas(a, b, p);
            System.out.println(res);
        }
    }
    static int lucas(long a, long b, int p) {
        if (a < p) return C((int)a, (int)b, p);
        else return (int)(1L * C((int)(a % p), (int)(b % p), p) * lucas(a / p, b / p, p) % p);
    }
    static int C(int a, int b, int p) {
        int res = 1;
        for (int i = 1, j = a; i <= b; i++, j--) {
            res = (int)(1L * res * j % p);
            res = (int)(1L * res * qmi(i, p-2, p) % p);
        }
        return res;
    }
    static int qmi(long a, long b, long p) {
        int res = 1;
        while (b > 0) {
            if ((b & 1) == 1) {
                res = (int)(res * a % p);
            }
            a = a * a % p;
            b >>= 1;
        }
        return res;
    }
}