leetcode::count_array_pairs_divisible_by_k::Solution类 参考

#include <leetcode.h>

静态 Public 成员函数
static long long	coutPairs (vector< int > &nums, int k)

详细描述

在文件 leetcode.h 第 1285 行定义.

成员函数说明

coutPairs()

long long leetcode::count_array_pairs_divisible_by_k::Solution::coutPairs ( vector< int > &  nums, int  k  )

static

在文件 leetcode.cpp 第 3243 行定义.

                                                              {
            long long ans = 0;
            // 统计每个数的倍数出现的次数
            auto count = unordered_map<int, int>();
            for(const auto num: nums) {
                count[num]++;
            }
            const int maximum = *max_element(nums.begin(), nums.end());
            // 为什么这个算法是 O(nlnn) 的？因为这个算法的循环次数是 n(1 + 1/2 + 1/3 + ...)，由调和级数可知括号内趋向 lnn
            for(int i = 1; i <= maximum; i++) {
                for(int j = i * 2; j <= maximum; j += i) {
                    count[i] += count[j];
                }
            }
            for(const auto num: nums) {
                // 对于每个数统计与它形成好二元组的数有几个
                ans += count[k / gcd(k, num)];
                if(static_cast<long long>(num) * num % k == 0) {
                    // 排除自己和自己形成好二元组的情况
                    ans--;
                }
            }
            return ans / 2;
        }

被这些函数引用 leetcode::count_array_pairs_divisible_by_k::TEST().

---

该类的文档由以下文件生成:

• leetcode.h
• leetcode.cpp