NEERC 1999 Divisibility /// 同余DP oj22640

发布时间：2020-12-14 04:49:44 所属栏目：大数据来源：网络整理

导读：题目大意：输入n,m；?( 1 ≤? N ?≤ 10000,2 ≤? M ?≤ 100 ) 接下来n个数；Each integer is not greater than 10000 by it‘s absolute value. 判断他们按顺序做加减法后能否整除m 若能输出“ Divisible ”，否则输出“ Not divisible ”； Sample Input S

题目大意：

输入n,m；?( 1 ≤?N?≤ 10000,2 ≤?M?≤ 100 )

接下来n个数；Each integer is not greater than 10000 by it‘s absolute value.

判断他们按顺序做加减法后能否整除m

若能输出“Divisible”，否则输出“Not divisible”；

Sample Input

Sample #1
4 7
17 5 -21 15

Sample #2
4 5
17 5 -21 15

Sample Output

Sample #1
Divisible

Sample #2
Not divisible

对于第一个样例解释：

17 + 5 + -21 + 15 = 16
17 + 5 + -21 - 15 = -14
17 + 5 - -21 + 15 = 58
17 + 5 - -21 - 15 = 28
17 - 5 + -21 + 15 = 6
17 - 5 + -21 - 15 = -24
17 - 5 - -21 + 15 = 48
17 - 5 - -21 - 15 = 18

-14可整除7

#include <bits/stdc++.h>
using namespace std;
bool dp[10005][105];
/// dp[i][j]表示第i个数时余数为j的状态存不存在 1为存在 0则不存在
int main()
{
    int n,m,a;
    while(~scanf("%d%d%d",&n,&m,&a))
    { 
        memset(dp,0,sizeof(dp));
        dp[1][(a%m+m)%m]=1;  // 到第1个数时 a%m 存在
        for(int i=2;i<=n;i++)
        {
            scanf("%d",&a);
            a=fabs(a); a%=m; /// 防止出现负数 先取绝对值 对求余没影响
            for(int j=0;j<m;j++)
                if(dp[i-1][j]) // 若上一个数时 余j 的状态存在 
                    dp[i][(j+a)%m]=dp[i][(j-a+m)%m]=1;
            /// 则可由 上个数余j的状态 推出
            /// 到当前数时(+a或-a) 余(j+a)%m 和 余(j-a+m)%m 
            /// 两个状态可存在
        }
        if(dp[n][0]) printf("Divisiblen");
        else printf("Not divisiblen");
    }

    return 0;
}

View Code

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!