Sgu/117

如果一个数X的M次方能整除K，那么它的每个质因子p的个数*M>=K包含的P的个数

这是一个很简单的快速幂运算

#include <iostream>
#include <stdio.h>
using namespace std;
 
int N, M, K;
int prime[6], pnum[6], cnt;
 
int main()
{
    scanf("%d %d %d", &N, &M, &K);
    int KK = K;
    for (int i = 2; i <= K; ++i)
        if (KK % i == 0)
        {
           prime[++cnt] = i;
           while (KK % i == 0)
           {
                 pnum[cnt]++;
                 KK /= i;
           }
           if (KK == 1) break;
        }
    int ans = 0, X;
    for (int i = 1; i <= N; ++i)
    {
        scanf("%d", &X);
        int flag = 1;
        for (int j = 1; j <= cnt; ++j)
        {
            int num = 0;
            while (X % prime[j] == 0)
            {
                  num++;
                  X /= prime[j];
            }
            if (num * M < pnum[j])
            {
               flag = 0;
               break;
            }
        }
        if (flag) ans++;
    }
    printf("%d", ans);
    return 0;
}
// From FingerSed

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
 
int n, m, k, tmp, sum = 0;
 
int fast_pow(int a, int b) {
	int res = 1;
	for ( ; b; b >>= 1) {
		if (b & 1)
			res = (long long)res * a % k;
		a = (long long)a * a % k;
	}
	return res;
}
 
int main() {
	scanf("%d %d %d", &n, &m, &k);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &tmp);
		if (fast_pow(tmp, m) % k == 0)
			sum++;
	}
	printf("%d\n", sum);
	return 0;
}