本文主要是介绍数论 - 整除问题 --- 整数集合中找出3的最大倍数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Mean:
题目描述：给一个包含非负整数的数组(长度为n)，找出由这些数字组成的最大的3的倍数，没有的话则输出impossible。
analyse:
首先想到的就是直接暴力，这是最蠢的方法，数据一大的话，必会TLE。
直接用蛮力的话，生成所有的组合，为 2^n个，对每个数字再进行比较判断，需要 O(n)的时间，因为n可能会比较大，需要每个位的比较。
总的时间复杂度为O(n * 2^n).
那么到底要怎么做呢？
首先我们来了解几个数学知识：
1)一个数n对m取余的余数为a1，b为n的每一位数字的和，那么有：n%m=b%m=a1。
例如，如果对于151和它的各位之和7，对于3的余数都为1。
2)一个数是3的倍数，则该数字各位总和为3的倍数。
例如，让我们考虑8760，它是3的倍数，因为数字总和为8 + 7 + 6 + 0 = 21，这是3的倍数。
推论：一个数是3的倍数，那么构成他的数字的排列为一个新的数字，这个数字仍然是3的倍数。
Time complexity：O(nlongn)
这篇关于数论 - 整除问题 --- 整数集合中找出3的最大倍数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
