Find amount of numbers for given sequence of integer numbers such that after raising them to the M-th power they will be divided by K.
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 than 10001) − on the second line.
Output
Write answer for given task.
Sample Input
1
2
4 2 50
9 10 11 12
Sample Output
1
1
Analysis
快速幂,时间复杂度为 O(nlogn),应该是可以过的。
要注意用 int 的话会溢出,所以我直接用了 unsigned long long。
这道题目还有一个方法是质因数分解,求出 M 次方以后的各个因数个数(就是把个因子个数乘以 M),然后和 M 的个因子的个数比较即可。