1195:判断整除
麦兜 / 2019-08-01 / 算法 / 阅读量 1748

【题目描述】

一个给定的正整数序列,在每个数之前都插入+
号或−号后计算它们的和。比如序列:1、2、4共有8

种可能的序列:

(+1) + (+2) + (+4) = 7
(+1) + (+2) + (-4) = -1
(+1) + (-2) + (+4) = 3
(+1) + (-2) + (-4) = -5
(-1) + (+2) + (+4) = 5
(-1) + (+2) + (-4) = -3
(-1) + (-2) + (+4) = 1
(-1) + (-2) + (-4) = -7

所有结果中至少有一个可被整数k
整除,我们则称此正整数序列可被k整除。例如上述序列可以被3、5、7整除,而不能被2、4、6、8……整除。注意:0、−3、−6、−9……

都可以认为是3的倍数。
【输入】

输入的第一行包含两个数:N(2<N<10000)
和k(2<k<100),其中N代表一共有N个数,k代表被除数。第二行给出序列中的N个整数,这些整数的取值范围都0到10000

之间(可能重复)。
【输出】

如果此正整数序列可被k
整除,则输出YES,否则输出NO

。(注意:都是大写字母)
【输入样例】

3 2
1 2 4

【输出样例】

NO

【来源】

No

如果按照题目给的样例去暴力破解 估计超时 所以要找出规律

4.png

样例代码:

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int main()
{
    int arr[10000];
    int n, k;
    cin >> n >> k;
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        sum += arr[i];
    }
    if (sum%k == 0)    /*总和*/
    {
        cout << "YES";
        return 0;
    }

    /*各项当成负数相加一次*/
    for (int i = 0; i < n; i++)
    {
        int Ssum = 0;
        for (int j = 0; j < n; j++)
        {
            if (j == i)
                Ssum += -arr[j];
            else {
                Ssum += arr[j];
            }
        }
        if (Ssum%k == 0)
        {
            cout << "YES";
            return 0;
        }
    }
    cout << "NO";
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。