题目
给出$n$个数 $a_1,a_2,\cdots,a_n$，求出有多少个整数对$(i,j)$，满足$1≤i<j≤n$，且$a_i$与$a_j$互质。
分析
Deepseek如是说：
直接方法的局限性
最直接的方法是检查所有可能的数对：
count = 0
for i in range(n):
for j in range(i+1, n):
if gcd(arr[i], arr[j]) == 1:
count += 1
这种方法的时间复杂度是O(n²)，当n很大时效率很低。
容斥原理的思路
基本思想
我们可以换个角度思考：所有数对的数量 - 不互质的数对数量
但是"不互质"的情况很复杂，因为两个数可能有多个公因数。
关键洞察
两个数互质 ⇔ 它们没有共同的质因数
我们可以用容斥原理来计数：
- 先计算所有数对
- 减去至少有1个公共质因数的数对
- 加回至少有2个公共质因数的数对（因为被减了两次）
- 减去至少有3个公共质因数的数对
- ...
莫比乌斯函数的作用
莫比乌斯函数μ(d)正好提供了我们需要的符号：
- μ(1) = 1
- 如果d有重复质因数，μ(d) = 0（不考虑这种情况）
- 如果d有k个不同质因数，μ(d) = (-1)^k
这正好对应容斥原理中各项的符号！
数学推导
公式
互质对的数量 = ∑ μ(d) × C(c_d, 2)
其中：
- d遍历所有可能的公约数（1到M）
- c_d = 能被d整除的数的个数
- C(c_d, 2) = 从c_d个数中选2个的组合数
为什么这个公式有效？
对于任意两个数a和b：
- 如果gcd(a,b) = 1，那么只有d=1时会被计数，贡献为μ(1)×1 = 1
- 如果gcd(a,b) = g > 1，那么对于g的每个因数d，这个数对都会被统计
通过莫比乌斯函数的性质，所有非互质对的贡献会相互抵消，只剩下互质对的贡献。
具体例子演示
假设数组为[2, 3, 4, 6]，最大数M=6。
步骤1：计算c_d
- d=1：所有数都能被1整除，c₁=4
- d=2：能被2整除的数有[2,4,6]，c₂=3
- d=3：能被3整除的数有[3,6]，c₃=2
- d=4：能被4整除的数有[4]，c₄=1
- d=5：没有数能被5整除，c₅=0
- d=6：能被6整除的数有[6]，c₆=1
步骤2：计算莫比乌斯函数
- μ(1) = 1
- μ(2) = -1（1个质因数）
- μ(3) = -1（1个质因数）
- μ(4) = 0（有平方因子2²）
- μ(5) = -1（1个质因数）
- μ(6) = 1（2个不同质因数2和3）
步骤3：应用公式
总互质对数 = μ(1)×C(4,2) + μ(2)×C(3,2) + μ(3)×C(2,2) + μ(4)×C(1,2) + μ(5)×C(0,2) + μ(6)×C(1,2)
= 1×6 + (-1)×3 + (-1)×1 + 0×0 + (-1)×0 + 1×0
= 6 - 3 - 1 = 2
验证
数组[2,3,4,6]的互质对：
- (2,3)：gcd=1 ✓
- (2,4)：gcd=2 ✗
- (2,6)：gcd=2 ✗
- (3,4)：gcd=1 ✓
- (3,6)：gcd=3 ✗
- (4,6)：gcd=2 ✗
确实有2个互质对，与计算结果一致。
算法优势
- 时间复杂度：O(M log M)，其中M是最大数
- 当n很大但M相对较小时，比O(n²)方法快很多
- 利用了数论性质，避免了重复计算
这就是为什么这个基于莫比乌斯函数和容斥原理的算法能够高效解决互质对计数问题。
题解（Possible）
#include<stdio.h>
#include<math.h>
int i,j,n,a[1000001],num[1000001]={1,1},p[1000001]={0},flag,pc=0,d[1000001]={0},mx=0,cnt[1000001]={0},t,mu,ans=0;
int main()
{
for(i=2;i<1000001;i++)
{
if(num[i]) continue;
num[i]=1,flag=0;
for(j=2;j<sqrt(i);j++)
{
if(!(i%j))
{
flag=1;
break;
}
}
if(flag) continue;
num[i]=0;
p[pc++]=i;
for(j=2;;j++)
{
if(i*j>1000000) break;
num[i*j]=1;
}
}
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
mx=mx>a[i]?mx:a[i];
for(j=1;j<=a[i];j++) if(!(a[i]%j)) d[j]++;
}
for(i=1;i<=mx;i++)
{
t=i,mu=1;
for(j=0;j<pc;j++)
{
if(!num[i])
{
cnt[i]++;
break;
}
if(!(t%p[j])) t/=p[j],cnt[i]++;
if(!(t%p[j]))
{
mu=0;
break;
}
if(t==1||t<p[j]) break;
}
if(mu) mu=cnt[i]%2?-1:1;
ans+=mu*d[i]*(d[i]-1)/2;
//printf("mu=%d d[%d]=%d\n",mu,i,d[i]);
}
printf("%d",ans);
return 0;
}