Problem C: Biving’s Numbers
Problem C: Biving’s NumbersTime Limit: 1 Sec Memory Limit: 32 MB
Submit: 76 Solved: 33
Biving loves her numbers. She always plays with them and treat them as her precious treasure.
Biving has N (1 <= N <= 13) numbers. One day, Biving wants to select K (1 <= K <= N) of them and wonders how many ways she can find such that the sum of these selected numbers have some common divisor with a given number M (1 <= M <= 10^7) besides 1.
The input contains several test cases (<= 100). Each test case have three integers in the first line: N, K and M. The next line contains N integers separated by a whitespace. Each number Ni will be in the following range: (1 <= Ni <= 10^7).
The output contains an integer, the answer for each case given in the input.
3 2 2
1 1 1
5 2 10
1 2 3 4 5