117.c

来自「平时acm训练时ac的源代码」· C语言 代码 · 共 64 行

/*
117. Counting 
Accepted 98 ms 114 kb 
*/

#include <stdio.h>

int main()
{
	int N, M, K, i, t, j, y, tc;
	int count=0, zysc=0;
	int zys[26][2];
	scanf("%d %d %d", &N, &M, &K);
	if (0==K%2)
	{
		zysc = 1;
		zys[0][0] = 2;
		zys[0][1] = 1;
		K=K/2;
		for (; 0==K%2;)
		{
			K=K/2;
			zys[0][1]++;
		}
	}
	for (i=3; 1!=K; i++)
	{
		if (0==K%i)
		{
			zys[zysc][0] = i;
			zys[zysc][1] = 1;
			K=K/i;
			for (; 0==K%i; )
			{
				K=K/i;
				zys[zysc][1]++;
			}
			zysc = zysc+1;
		}
	}
	for (i=0; i<N; i++)
	{
		scanf("%d", &t);
		for (y=1, j=0; j<zysc; j++)
		{
			for (tc=0; 0==t%zys[j][0]; )
			{
				t = t/zys[j][0];
				tc++;
			}
			if (tc*M<zys[j][1])
			{
				y=0;
				break;
			}
		}
		if (1==y)
		{
			count = count+1;
		}
	}
	printf("%d", count);
}