能看见处的树当且仅当互质。否则,设他们的非1公因数为共线,就会被遮挡。

那么答案就是求以内的互质的数的对数。

在这对数中,有一些数对的最大公因数不是1,我们应该想办法减去这些数对的贡献。减去至少有2作为公因数的数对、减去至少有3作为公因数的数对、再加回有6作为公因数的数对……这个过程其实就是在做莫比乌斯反演。

定义

那么有关系

进行莫比乌斯反演,

答案其实就是

预处理出的值,就可以求了。

还有另外一种无脑一点的套路。直接利用,这个恒等式可以将条件式转换为求和式。

这道题其实可以出多组数据,用杜教筛的话还可以做。不过和课程好像关系不大。