887. 求组合数 III（模板 卢卡斯定理）

a,b都非常大，但是p较小

前边两种方法都会超时的  N^2 和NlongN

 可以用卢卡斯定理  P*longN*longP

    定义：

代码：

import java.util.Scanner;

public class Main{

        static int p;

        //快速幂

        static long quick_pow(long a,long b){

                long res=1;

                while(b>0){

                        if((b&1)==1) res=res*a%p;

                        a=a*a%p;

                        b>>=1;

                }

                return res;

        }

        //根据组合数定义求C（a,b）

        static long C(long a,long b){

                long res=1;

                for(long i=1,j=a;i<=b;i++,j--){

                        res=res*j%p;

                        res=res*quick_pow(i,p-2)%p;

                }

                return res;

        }

        //卢卡斯定理

        static long lucas(long a,long b){

                if(a<p && b<p) return C(a,b);

                return C(a%p,b%p)*lucas(a/p,b/p)%p;

        }

        public static void main(String[] args) {

                Scanner scan=new Scanner(System.in);

                int t=scan.nextInt();

                while(t-->0){

                        long a=scan.nextLong();

                        long b=scan.nextLong();

                        p=scan.nextInt();

                        System.out.println(lucas(a,b));

                }

        }

}