Skip to content

Latest commit

 

History

History
 
 

2198.Number-of-Single-Divisor-Triplets

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

2198.Number-of-Single-Divisor-Triplets

本题的突破口在于数据约束:nums的数量很大,但是每个数字的数值很小,只有[1,100]。所以我们用三重循环来枚举每个数字可能的数值,复杂度上都是可以接受的。

我们在枚举三个数值a,b,c的时候,需要注意一个问题,那就是这三个数值是否可以相等。

如果三个数值彼此不等,那么(i,j,k)的组合数目就是count[a]*count[b]*count[c],其中count[a]表示数值a在数组里出现了几次(即对应了不同的index)。但是注意本题求的是排列数,所以还要在刚才的数字上乘以6,即给定三个index的排列方式。

如果三个数值中有两个数值相等,不妨设为a,a,b,那么(i,j,k)的组合数目就是count[a]*count[a]/2*count[b],这是因为我们要在所有数值为a的元素中挑出任意两个不同的index。注意我们最终拿出来的(i,j,k)还是三个不同的index,所以排列方式还是6.

如果三个数值都相等的话,会发生什么呢?事实上这是不可能的。三个数值都相等的时候,这三个数值一定都能整除他们的和,不符合条件。