2405852_ac_462ms_4392k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>

int m,n;
int Opt[10010][110];
int Int[10010];

int DP()
{
    int i,j,s;
    memset(Opt,0,sizeof(Opt));
    Opt[1][Int[1]]=1;
    for(i=1;i<n;i++)
	{
        for(j=0;j<=m;j++)
        {
            if(Opt[i][j])
            {
                s=j+Int[i+1];
                s%=m;
                Opt[i+1][s]=1;
                s=j-Int[i+1];
				s%=m;
                while(s<0) 
					s+=m;
                Opt[i+1][s]=1;
            }
        }
    }
    if(Opt[n][0]) 
		return 1;
    return 0;
}
int main()
{
    int i;

    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
{
            scanf("%d",&Int[i]);
            Int[i]%=m;
            while(Int[i]<0) 
                Int[i]+=m;
        }
        if(DP()) 
			printf("Divisible\n");
        else 
			printf("Not divisible\n");
    return 0;
}