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

如果一个数组满足长度至少是 $A_iAi 和 A_j (i ot = j)Aj(i�=j) 其和 A_i+A_jAi+Aj 都是 KK 的倍数，我们就称该数组是完美 KK 倍数组。$

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

如果这样的子数组不存在，输出

输入格式

第一行包含两个整数

第二行包含 $A_1, A_2, ... A_NA1,A2,...AN。$

$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 }