2001.可互换矩形的组数

链接：2001.可互换矩形的组数
难度：Medium
标签：数组、哈希表、数学、计数、数论
简介：计算并返回 rectangles 中有多少对 可互换 矩形。

题解 1 - cpp

• 编辑时间：2022-01-07
• 执行用时：500ms
• 内存消耗：134.5MB
• 编程语言：cpp
• 解法介绍：统计最简比例的个数。

int gcd(int a, int b) {
    if (b) return gcd(b, a % b);
    return a;
}
class Solution {
   public:
    struct Data {
        int a, b;
        Data(int a, int b) : a(a), b(b) {
            int c = gcd(a, b);
            this->a /= c;
            this->b /= c;
        }
        bool operator<(const Data &obj) const {
            if (a != obj.a) return a < obj.a;
            return b < obj.b;
        }
    };
    long long interchangeableRectangles(vector<vector<int>> &rectangles) {
        map<Data, int> m;
        long long ans = 0;
        for (auto &x : rectangles) {
            Data d(x[0], x[1]);
            ans += m[d];
            m[d] += 1;
        }
        return ans;
    }
};