202503021830 完美K倍数组--相加和为K倍数

完美K倍数组—相加和为K倍数

完美K倍子数组 - 题库 - 计蒜客 (jisuanke.com) 如果一个数组满足长度至少是 2 ，并且其中任意两个不同的元素 A1  和 A2  其和 A1 + A2 都是 K 的倍数，我们就称该数组是完美 K 倍数组。

需要数组中所有数都满足那个条件,也就是说任何一个数 A1 都要让其他数都满足 A2。

很明显最长的长度就是 A1 + A1 为 k 时, 这样每一个数加上其他数都满足, 或者 A1 == k。

若没有 A1 + A1 = K 的, 且存在 A1 + A2 = K, 那么长度就是 2。 若也没有 A1 + A2 = k, 则不存在。

因 1 + 3 = 4 是 2 的倍数, 可以看出, 将 A1 % K 与 A2 % k 相加为 k 就是判定条件。

#include<iostream>
#include <cstring>
#include <string>
#include <unordered_map>
using namespace std;
typedef long long LL;
unordered_map<LL,LL> map;
LL maxx;
bool flag;
int main()
{
    LL n, k;
    cin >> n >> k;
    for(int i = 0 ; i < n; i++)
    {
        LL t;
        cin >> t;
        t = t % k;
        if(t == 0) {map[t]++; maxx = max(maxx, map[t]);}
        else if (t * 2 == k) {map[t]++; maxx = max(maxx, map[t]);}
        else if(!flag)
        {
            map[t] = 1;
            if(map[k - t]) flag = 1;
        }
    }
    if(maxx <= 2 && !flag) cout << -1 << endl;
    else if(maxx > 2) cout << maxx << endl;
    else cout << 2 << endl;
    return 0;
}