You are given?n?rectangles represented by a?0-indexed?2D integer array?rectangles, where?rectangles[i] = [widthi, heighti]?denotes the width and height of the?ith?rectangle.

Two rectangles?i?and?j?(i < j) are considered?interchangeable?if they have the?same?width-to-height ratio. More formally, two rectangles are?interchangeable?if?widthi/heighti?== widthj/heightj?(using decimal division, not integer division).

Return?the?number?of pairs of?interchangeable?rectangles in?rectangles.

?

Example 1:

Input: rectangles = [[4,8],[3,6],[10,20],[15,30]]

Output: 6

Explanation: The following are the interchangeable pairs of rectangles by index (0-indexed):

- Rectangle 0 with rectangle 1: 4/8 == 3/6.?

- Rectangle 0 with rectangle 2: 4/8 == 10/20.?

- Rectangle 0 with rectangle 3: 4/8 == 15/30.?

- Rectangle 1 with rectangle 2: 3/6 == 10/20.?

- Rectangle 1 with rectangle 3: 3/6 == 15/30.?

- Rectangle 2 with rectangle 3: 10/20 == 15/30.

Example 2:

Input: rectangles = [[4,5],[7,8]]

Output: 0

Explanation: There are no interchangeable pairs of rectangles.

其實(shí)只要會最大公約數(shù)這個(gè)函數(shù)即可，這樣15 30，跟10 20這一組就是同一類的，然后map存儲每個(gè)的數(shù)量，最后用排列算出來，返回；

?

Constraints:

• n == rectangles.length

• 1 <= n <= 105

• rectangles[i].length == 2

• 1 <= widthi, heighti?<= 105

Runtime:?123 ms, faster than?8.98%?of?Java?online submissions for?Number of Pairs of Interchangeable Rectangles.

Memory Usage:?93.1 MB, less than?34.28%?of?Java?online submissions for?Number of Pairs of Interchangeable Rectangles.