117. Counting
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
Find amount of numbers for given sequence of integer numbers such that after raising them to theM-th power they will be divided byK.
Input
Input consists of two lines. There are three integer numbers
N, M, K (0<N, M, K<10001) on the first line. There are N positive integer numbers − given sequence (each number is not more than10001) − on the second line.
Output
Write answer for given task.
Sample Input
4 2 50 9 10 11 12
Sample Output
1
给出n个数，A[1]^m...A[n]^m中能被k整除的数的个数
9^2 = 81 10^2 = 100 11^2 = 121 12^2 = 144 其中能被50整除的只有一个100
题解：拿10举例，可以对10进行质因数分解 得到 2 5 那么 10^2就是 2*2 * 5*2， 再对50进行质因数分解 2*1 * 5*2 相应因子项的系数比10^2要小，所以成立
或者直接矩阵快速幂