第九届蓝桥杯——倍数问题（数论、枚举）

水深无声 2022-12-10 10:15 114阅读 0赞

### 倍数问题 ###

众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。但小葱 只擅长两个数的情况，当有很多个数之后就会比较苦恼。现在小葱给了你 n 个数，希望你 从这 n 个数中找到三个数，使得这三个数的和是 K 的倍数，且这个和最大。数据保证一 定有解。

输入  
从标准输入读入数据。 第一行包括 2 个正整数 n,K。  
第二行 n 个正整数，代表给定的n 个数。  
输出  
输出到标准输出。 输出一行一个整数代表所求的和。

样例  
输入  
4 3  
1 2 3 4  
输出  
9

数据约定  
对于 30% 的数据，n <= 100。  
对于 60% 的数据，n <= 1000。  
对于另外 20% 的数据，K <= 10。  
对于 100% 的数据，1 <= n <= 105, 1 <= K <= 103，给定的 n 个数均不超过 108。

--------------------

数论小知识  
当三个数 v1, v2, v3 的和为 K 的倍数时  
(v1+v2+v3)%K=0

利用上面数论的知识，我们要创建一个二维数组 group 存储数据。存储关系：余数与数据。  
eg：假如我们要存储一个数 5，K 为 4。  
那么这个数将会存储在 group\[5%4\]\[0\] = 5

特殊情况分析：  
①、可能取相同余数的情况，所以我们要对每个余数对应的数据进行排序，使得每次取的数都是最大的。  
②、题目仅要取三个数，所以我们只要维护每个余数对应前三大的数据。  
eg:1 3 4 5 6 那么前三大就是 6 5 4。

--------------------

AC代码

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    int n, k;
    int group[1000][3];
    ll ans=0;
    
    
    int main(){ 
    	cin>>n>>k;
    	
    	//直接分组
    	memset(group, 0, sizeof(group)); 
    	for(int i=0; i<n; i++){ 
    		int x;
    		cin>>x;
    		int re = x % k;
    		
    		if(x > group[re][0]){ 
    			group[re][2] = group[re][1];
    			group[re][1] = group[re][0];
    			group[re][0] = x;
    		}
    		else if(x > group[re][1]){ 
    			group[re][2] = group[re][1];
    			group[re][1] = x; 
    		}
    		else if(x > group[re][2]){ 
    			group[re][2] = x;
    		}
    	}
    	
    	int v1, v2, v3;
    	for(int i=0; i<k; i++){ 
    		v1 = group[i][0];
    		if(v1!=0){ 
    			for(int j=i; j<k; j++){ 
    				if(i==j)
    					v2 = group[j][1];
    				else
    					v2 = group[j][0];
    					
    				if(v2!=0){ 
    					int z = (k-(i+j)%k)%k;
    					if(i!=j){ 
    						if(z!=j&&z!=i)
    							v3 = group[z][0];
    						else if(z==j)
    							v3 = group[j][1];
    						else if(z==i)
    							v3 = group[i][1];
    					}
    					else{ 
    						if(z==i)
    							v3 = group[z][2];
    						else
    							v3 = group[z][0];
    					}
    					if(v3!=0)
    						ans = max((ll)v1+v2+v3, ans);
    				}
    			}
    		}
    	}
    	cout<<ans;
    	
    	return 0;
    }

#### 总结 ####

这道题说难也不难，考察数论基础以及如何实现题目要求。  
简单的东西一定要掌握好，基础由为重要。

如果对你有帮助，请给我个赞吧：)