1900D
CF1900D Small GCD 题解
原题链接:CF1900D,题意不多赘述。 首先可以将 \(a\) 数组排序,并且枚举中间的那个数 \(a_i\)。那么答案就是 \(\sum_{j=1}^{i-1} \gcd(a_j,a_i)\times (n-i)\)。重点在于求前面的 \(\gcd\)。可以用欧拉反演,但是也可以不用,因为我不会 ......
CF1900D Small GCD
Link 这是一个需要欧拉反演的题目 首先,可以知道只和数字之间的大小有关,数列的顺序无关,那么就可以首先排一个序方便解决该问题。 根据欧拉函数的性质,知道\(n=\sum_{d|n}\phi{(n)}\) 那么我们每次先确定中间的数\(a_j\),然后根据公式,得他它得贡献是\(\sum_{i=1 ......
CodeForces 1900D Small GCD
洛谷传送门 CF 传送门 不是很懂官方题解在干嘛。 设 \(g_x\) 为满足 \(x \mid \gcd(a_i, a_j, a_k)\) 且 \(i, j, k\) 两两不同的所有无序三元组的 \(f(a_i, a_j, a_k)\) 之和。则很容易容斥求出 \(h_x\) 为 \(x = \g ......