有两种做法
第一种做法：欧拉反演（其实我赛时的时候是想到了欧拉反演的，但是我不太清楚欧拉反演的使用trick）
欧拉反演的trick见这篇文章
欧拉反演直接用在gcd上还是挺多的，可以想一下\(cnt\)数组怎么求
\(cnt\)数组其实是只用记一维的（因为记两维肯定爆炸了）。考虑对于\(d\)，如果\(d\)不是\(a_i\)的约数，那么\(d\)在\(i\)的\(cnt\)和\(d\)在\(i-1\)的\(cnt\)肯定是一样的；如果\(d\)是\(a_i\)的约数，那么\(d\)在\(i\)的\(cnt\)就多了\(1\)
第二种做法：考虑贡献
见这篇文章
由于这道题目给的序列是离散的，我们没办法利用欧拉函数，所以考虑贡献的时候只能求出前面有多少个\(a_i\)满足gcd是\(x\)，那么\(x\)肯定是\(a_i\)的约数，但是这样的\(a_i\)与\(a_j\)的gcd却不一定是\(x\)，但是我们有结论，公约数一定是gcd的约数，所以我们用容斥减去更大\(g\)就好了
标签：约数,cnt,GCD,反演,Small,欧拉,gcd From： https://www.cnblogs.com/dingxingdi/p/18059758