方法思路

1. 对于点(i, a[i])和点(j, a[j])，连线经过原点的条件是：a[i]/i = a[j]/j，即斜率相等
2. 等价于 a[i]*j = a[j]*i
3. 为了避免浮点数精度问题，我们可以使用分数表示斜率，即a[i]/i的最简形式
4. 对于每个点，计算其与原点连线的斜率a[i]/i的最简形式
5. 使用哈希表统计相同斜率的点的数量，然后计算点对数
6. 如果有k个点具有相同斜率，那么它们可以形成k*(k-1)/2个点对

代码实现

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        scanner.close();
        
        System.out.println(countPairs(n, a));
    }
    
    private static long countPairs(int n, int[] a) {
        // 使用Map存储斜率及其对应的点数
        Map<String, Integer> slopes = new HashMap<>();
        
        for (int i = 1; i <= n; i++) {
            // 计算斜率a[i-1]/i的最简形式
            int g = gcd(a[i-1], i);
            String slope = (a[i-1]/g) + "/" + (i/g);
            slopes.put(slope, slopes.getOrDefault(slope, 0) + 1);
        }
        
        // 计算点对数
        long totalPairs = 0;
        for (int count : slopes.values()) {
            totalPairs += (long) count * (count - 1) / 2;
        }
        
        return totalPairs;
    }
    
    private static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

Python

from collections import defaultdict
import math

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def count_pairs(n, a):
    # 存储斜率及其对应的点数
    slopes = defaultdict(int)
    
    for i in range(1, n+1):
        # 计算斜率a[i-1]/i的最简形式
        g = gcd(a[i-1], i)
        slope = (a[i-1]//g, i//g)
        slopes[slope] += 1
    
    # 计算点对数
    total_pairs = 0
    for count in slopes.values():
        total_pairs += count * (count - 1) // 2
    
    return total_pairs

n = int(input())
a = list(map(int, input().split()))
print(count_pairs(n, a))

C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
using namespace std;

int gcd(int a, int b) {
    while (b) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

long long countPairs(int n, vector<int>& a) {
    unordered_map<string, int> slopes;
    
    for (int i = 1; i <= n; i++) {
        // 计算斜率a[i-1]/i的最简形式
        int g = gcd(a[i-1], i);
        string slope = to_string(a[i-1]/g) + "/" + to_string(i/g);
        slopes[slope]++;
    }
    
    // 计算点对数
    long long totalPairs = 0;
    for (const auto& pair : slopes) {
        long long count = pair.second;
        totalPairs += count * (count - 1) / 2;
    }
    
    return totalPairs;
}

int main() {
    int n;
    cin >> n;
    
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    cout << countPairs(n, a) << endl;
    
    return 0;
}