6355: 三元组

给出一个长度为n的序列，问存在多少个三元组满足ai x aj = ak (i, j, k可以相同)。（1 <= n <= 1e⁶, 1 <= ai <= 1e⁶）

本题由于对 i , j , k 大小关系无要求，因此需要考虑排列组合的方式。在数组中，找某个数的约数是否存在比判断两数之积是否存在更方便一些，因此可遍历判断某数的约数是否在数组中成对出现。

本题对时间复杂度较为严格，需要控制在 nlogn ，因此对于数组中的重复元素需要进行跳步，即记录个数进行相乘。而对于 i，j，k 的特殊性，当该对约数并不相等时，还需要乘 2 对排列组合进行考虑。

：若要满足题目条件，那么ai x aj必须要小于或等于序列中最大值或1e6均可，可以用hash表记录每个数值出现的次数，最后枚举i、j来得到k，在枚举的过程中i需要从1~1e6，而j的范围则是i * j <= maxv或1e6，这样时间复杂度可以达到O(n * sqrt(n))。

1. ps：这题卡map。哈希表不能用map来存；