题意
给定一个长度为 \(n\) 的正整数数列 \(a\)，求
\[\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{n} \gcd\left(a_i, a_j\right) \times \gcd\left(i, j\right)
\]
（\(1 \le n,a_i \le 10^5\)）。
题解
根据欧拉函数的性质，可以得出
\[n = \sum\limits_{d \mid n} \varphi(d)
\]
该式也被称作欧拉反演。
下面开始化简算式
\[\begin{aligned}
Ans &= \sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{n} \gcd\left(a_i, a_j\right) \times \gcd\left(i, j\right) \\
&= \sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{n} \gcd\left(a_i, a_j\right) \times \sum\limits_{d \mid \gcd\left(i, j\right)} \varphi(d) \\
&= \sum\limits_{d = 1}^{n} \varphi(d) \sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{n} \gcd\left(a_i, a_j\right) \left[d \mid \gcd\left(i, j\right)\right] \\
&= \sum\limits_{d = 1}^{n} \varphi(d) \sum\limits_{i = 1}^{n} \left[d \mid i\right]\sum\limits_{j = 1}^{n} \left[d \mid j\right]\gcd\left(a_i, a_j\right) \\
&= \sum\limits_{d = 1}^{n} \varphi(d) \sum\limits_{i = 1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j = 1}^{\lfloor\frac{n}{d}\rfloor} \gcd\left(a_{id}, a_{jd}\right) \\
&= \sum\limits_{d = 1}^{n} \varphi(d) \sum\limits_{i = 1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j = 1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{t \mid \gcd\left(a_{id}, a_{jd}\right)} \varphi(t) \\
&= \sum\limits_{d = 1}^{n} \varphi(d) \sum\limits_{t} \varphi(t) \sum\limits_{i = 1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j = 1}^{\lfloor\frac{n}{d}\rfloor}\left[t \mid \gcd\left(a_{id}, a_{jd}\right)\right] \\
&= \sum\limits_{d = 1}^{n} \varphi(d) \sum\limits_{t} \varphi(t) \sum\limits_{i = 1}^{\lfloor\frac{n}{d}\rfloor}\left[t \mid a_{id}\right]\sum\limits_{j = 1}^{\lfloor\frac{n}{d}\rfloor}\left[t \mid a_{jd}\right] \\
&= \sum\limits_{d = 1}^{n} \varphi(d) \sum\limits_{t} \varphi(t) \left(\sum\limits_{i = 1}^{\lfloor\frac{n}{d}\rfloor}\left[t \mid a_{id}\right]\right)^2 \\
\end{aligned}\]
我们先枚举 \(d\) 和 \(id\)，复杂度为 \(\mathcal{O}(n \ln n)\)。如果我们在枚举 \(t\) 时可以保证只枚举 \(a_{id}\) 的因子，那么总复杂度为 \(\mathcal{O}(n \ln n \max\limits_{i = 1}^{n} d(a_i))\)，其中 \(d(n) = \sum\limits_{i \mid n} 1\) 即 \(n\) 的约数个数，可以通过本题。
Code
//Codeforces - 1575G
#include <bits/stdc++.h>
typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::vector<bool> bitset;
constexpr valueType MOD = 1e9 + 7;
template<typename T1, typename T2, typename T3 = valueType>
void Inc(T1 &a, T2 b, const T3 &mod = MOD) {
a = a + b;
if (a >= mod)
a -= mod;
}
template<typename T1, typename T2, typename T3 = valueType>
T1 mul(T1 a, T2 b, const T3 &mod = MOD) {
return (long long) a * b % MOD;
}
class LineSieve {
public:
typedef std::vector<valueType> container;
private:
valueType size;
bitset isPrime;
container primeList, phi;
ValueMatrix fact;
public:
explicit LineSieve(valueType _size_) : size(_size_), isPrime(_size_ + 1, true), phi(_size_ + 1), fact(_size_ + 1) {
phi[1] = 1;
for (valueType i = 2; i <= size; ++i) {
if (isPrime[i]) {
primeList.push_back(i);
phi[i] = i - 1;
}
for (auto const &iter: primeList) {
valueType const t = i * iter;
if (t > size)
break;
isPrime[t] = false;
if (i % iter == 0) {
phi[t] = phi[i] * iter;
break;
} else {
phi[t] = phi[i] * (iter - 1);
}
}
}
for (valueType i = 1; i <= size; ++i) {
for (valueType j = i; j <= size; j += i) {
fact[j].push_back(i);
}
}
}
const container &Prime() const {
return primeList;
}
valueType Phi(valueType x) const {
if (x > size)
throw std::range_error("Larger than Size.");
if (x < 1)
throw std::range_error("Too small.");
return phi[x];
}
const container &Factor(valueType x) const {
if (x > size)
throw std::range_error("Larger than Size.");
if (x < 1)
throw std::range_error("Too small.");
return fact[x];
}
};
constexpr valueType V = 1e5 + 5;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
LineSieve const sieve(V);
valueType N;
std::cin >> N;
ValueVector source(N + 1, 0);
for (valueType i = 1; i <= N; ++i)
std::cin >> source[i];
valueType ans = 0;
ValueVector count(V, 0);
for (valueType d = 1; d <= N; ++d) {
for (valueType i = d; i <= N; i += d)
for (auto const &iter: sieve.Factor(source[i]))
++count[iter];
valueType sum = 0;
for (valueType i = d; i <= N; i += d) {
for (auto const &iter: sieve.Factor(source[i])) {
if (count[iter] > 0) {
Inc(sum, mul(mul(count[iter], count[iter]), sieve.Phi(iter)));
count[iter] = 0;
}
}
}
Inc(ans, mul(sum, sieve.Phi(d)));
}
std::cout << ans << std::endl;
return 0;
}