pku1745.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 64 行

#include <stdio.h>

int st[10000][100];

int Nu[10000];

int N, K;

int Calc(int x)
{
	x %= K;
	if (x < 0)
	{
		x += K;
	}
	return x;
}

int main()
{
	int i, j;
	while (scanf("%d%d", &N, &K) != -1)
	{
		for (i = 0; i < N; i++)
		{
			scanf("%d", &Nu[i]);
		}

		if (N == 1)
		{
			if (Nu[0] % K == 0)
			{
				printf("Divisible\n");
			}
			else
			{
				printf("Not divisible\n");
			}
			continue;
		}
		memset(st, 0, sizeof(st));
		st[0][Calc(Nu[0])] = 1;
		for (i = 1; i < N; i++)
		{
			for (j = 0; j < K; j++)
			{
				if (st[i - 1][j])
				{
					st[i][Calc(j + Nu[i])] = 1;
					st[i][Calc(j - Nu[i])] = 1;
				}
			}
		}
		if (st[N - 1][0])
		{
			printf("Divisible\n");
		}
		else
		{
			printf("Not divisible\n");
		}
	}
	return 0;
}