hdu 5072莫比乌斯反演题意：给出n个数a1,a2,…,an, 从中选出三个数a,b,c,且这三个数符合[(a,b)=(b,c)=(a,c)=1] || [(a,b)!=1 && (b,c)!=1 && (a,c)!=1] 其中(x,y)表示x,y的最大公约数。求符合这个条件的三元组的个数。限制：3 <= n <= 1e5; 1 <= ai <= 1e5思路：设bi为与ai互质的数的个数，则符合条件 !(((a,b)=(b,c)=(a,c)=1) || ((a,b)!=1 && (b,c)!=1 && (a,c)!=1)) 的三元组的个数为：t=(sigma(1~n)bi*(n-1-bi))/2可以看到C(n,3)-t即为答案。下面证明上面式子的由来：对于任意符合条件的a,b,c有以下6种情况：1. (a,b)=1 && (a,c)!=1 && (b,c)=12. (a,b)=1 && (a,c)!=1 && (b,c)!=13. (a,b)!=1 && (a,c)=1 && (b,c)=14. (a,b)!=1 && (a,c)=1 && (b,c)!=15. (a,b)=1 && (a,c)=1 && (b,c)!=16. (a,b)!=1 && (a,c)!=1 && (b,c)=1我们可以发现bi*(n-1-bi)只覆盖了上面的1~4的情况，但我们又发现剩下两种情况可以由b或c来覆盖其实对于1~6的情况，，每种情况都被覆盖了两遍1. 被a,c覆盖2. 被a,b覆盖…所以是所有的加起来/2然后问题就被化简为对于每个数，在复杂度内求和它互质的数的个数，这个可以用容斥做，也可以用莫比乌斯反演来做对于一个给定的数x0设f(k)为gcd(x0,x)=k的x的数目设F(k)为gcd(x0,x)为k的倍数的x的数目，然后发现F(k)为拥有因子k的ai的数目，这个可以用O(sqrt(ai))枚举因子预处理出来。
踮起脚尖，我们就能离幸福更近点吗？
