计蒜客-T1271 完美K倍子数组

如果一个数组满足长度至少是 22 ，并且其中任意两个不同的元素 A_iAi 和 A_j (i \not = j)Aj(i=j) 其和 A_i+A_jAi+Aj 都是 KK 的倍数，我们就称该数组是完美 KK 倍数组。

现在给定一个包含 NN 个整数的数组 A = [A_1, A_2, ... A_N]A=[A1,A2,...AN] 以及一个整数 KK，请你找出 AA 的最长的完美子数组 BB，输出 BB 的长度。

如果这样的子数组不存在，输出 -1−1。

输入格式

第一行包含两个整数 NN 和 KK。

第二行包含 NN 个整数 A_1, A_2, ... A_NA1,A2,...AN。

1 \le N \le 1000001≤N≤100000

1 \le A_i, K \le 10000000001≤Ai,K≤1000000000

输出格式

一个整数，表示答案。

输出时每行末尾的多余空格，不影响答案正确性

样例输入

5 3

1 3 2 3 6

样例输出

题解：

我原本想的是把每一个输入的数x都取余于k，然后把r[x]++（r是一个map容器，记录x出现的次数）,然后k-x与x放在一起不久刚好是k的倍数了吗。。。但是我没有考虑如果x+x不是k的倍数

就比如k==4,如果n==4为1，1，3，3，那么r[1]=2,r[3]=2,那么这个集合长度不能为4只能为2，因为如果集合长度为4，那么1+1=2就不是4的倍数

所以如果r[x]>0且r[k-x]>0,那么集合长度最小为2.要特别注意一下r[0],和当k为偶数时r[k/2],这两个单独自己就可以构成k倍数组

代码：

 1 #include<stdio.h>

 2 #include<string.h>

 3 #include<iostream>

 4 #include<algorithm>

 5 #include<math.h>

 6 #include<vector>

 7 #include<queue>

 8 #include<map>

 9 using namespace std;

10 typedef long long ll;

11 const int maxn=1e5;

12 const int INF=0x3f3f3f3f;

13 map<ll,ll>r;

14 map<ll,ll>::iterator it;

15 int main()

16 {

17     ll n,k,tmp,maxx;

18

19     cin>>n>>k;

20

21     ll cnt1=0,cnt2=0,flag=0;

22

23     for(ll i=0;i<n;++i){

24

25         cin>>tmp;

26

27         int t=tmp%k;

28

29         if(t==0) r[t]++,maxx=max(maxx,r[t]);

30

31         else if(2*t%k==0) r[t]++,maxx=max(maxx,r[t]);

32

33         else if(!flag){

34

35             r[t]=1;

36

37             if(r[k-t]) flag=1;

38

39         }

40

41     }

42     if(maxx<2 && !flag) cout<<-1<<endl;

43     else if(maxx>=2) cout<<maxx<<endl;

44     else cout<<2<<endl;

45     return 0;

46 }

巴特西

计蒜客-T1271 完美K倍子数组

输入格式

输出格式

最新文章

热门文章