by THU

B(G)

C(W)

n个数中选3个数,求使得这三个数两两间gcd = 1gcd != 1的方案数

数论

由于数的范围较小,所以可以用容斥处理出与每个数不互质的数的个数cur
然后其可以组成的不满足组数为 (cur-1)*(n-cur)

然后考虑重复的情况,a为当前数,假设a与b互质,与c不互质,
若b,c不互质,那么在b为当前数时会选择 a,c
若b,c互质,那么在c为当前数时会选择 a,b
所以无论如何都只重复选了一次

复杂度 $O(nsqrt(n))$

D(W)

E(W)

I(W)