[原创]HDU 5446 Unknown Treasure [lucas+CRT]【数论】

2016-08-11 20:13:29 Tabris_ 阅读数：224

https://blog.csdn.net/qq_33184171/article/details/52186122

------------------------------.
Unknown Treasure

Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 2196 Accepted Submission(s): 814

Problem Description
On the way to the next secret treasure hiding place, the mathematician discovered a cave unknown to the map. The mathematician entered the cave because it is there. Somewhere deep in the cave, she found a treasure chest with a combination lock and some numbers on it. After quite a research, the mathematician found out that the correct combination to the lock would be obtained by calculating how many ways are there to pick m different apples among n of them and modulo it with M. M is the product of several different primes.

Input
On the first line there is an integer T(T≤20) representing the number of test cases.

Each test case starts with three integers n,m,k(1≤m≤n≤10^18,1≤k≤10) on a line where k is the number of primes. Following on the next line are k different primes p1,…,pk. It is guaranteed that M=p1⋅p2⋅⋅⋅pk≤10^18 and pi≤10^5 for every i∈{1,…,k}.

Output
For each test case output the correct combination on a line.

Sample Input
1
9 5 2
3 5

Sample Output
6
------------------------------.

------------------------------.