T3
数组中求满足条件的对数:相同的数字或和能被m整除。
如果只有和能被m整除,我们可以维护一个长为m的数组mod_cnts,将数字按照模m的余数分组,然后遍历即可。现在多了一个可能的条件,我们可以把这个条件用另一个长为m的数组rep_cnts记录下来,rep_cnts[i]表示模m余i的数字中,两两相同的对数有多少。
那么当处理模m余i的数字时,和它成对的数要么在模m余i的集合中,要么在模m余m-i的集合中。对于模m余m-i的数字同理。那么我们优先让模m余i的数字和模m余m-i的数字两两结合,剩余的数字依据rep_cnts让它跟自己结合。
时间复杂度O(max(m, n)),空间复杂度O(max(m, n))。