本文共 1846 字，大约阅读时间需要 6 分钟。

为了解决这个问题，我们需要计算给定数组中互素数对的数量。互素数对指的是两个数的最大公约数为1的对。我们可以利用莫比乌斯函数和容斥原理来高效地解决这个问题。

方法思路

解决代码

#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
       
using namespace std;
const int MAXN = 100010;
int mu[MAXN];
void compute_mobius(int n) {
    mu[1] = 1;
    vector
       
         is_prime(n + 1, true);
    is_prime[1] = false;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            for (int j = i; j <= n; j += i) {
                is_prime[j] = false;
                mu[j] = -mu[j / i];
                if (j % i == 0) {
                    mu[j] = 0;
                }
            }
        }
    }
}
int main() {
    compute_mobius(MAXN);
    while (~scanf("%d", &n)) {
        vector
        
          a(n); for (int i = 0; i < n; ++i) { scanf("%d", &a[i]); } int max_a = *max_element(a.begin(), a.end()); vector
         
           freq(max_a + 1, 0); for (int num : a) { freq[num]++; } vector
          
            cnt(max_a + 1, 0); for (int d = 1; d <= max_a; ++d) { for (int j = d; j <= max_a; j += d) { cnt[d] += freq[j]; } } long long ans = 0; for (int d = 1; d <= max_a; ++d) { if (cnt[d] >= 2) { ans += (cnt[d] * (cnt[d] - 1) / 2) * mu[d]; } } cout << ans << endl; } return 0; }
          
         
        
       
      
     
    
   

代码解释

这种方法高效地解决了问题，能够在合理的时间和空间复杂度内处理大规模输入。