\(\mathcal{Description}\)

给定 \(\{a_n\}\)，求：

\[\sum_{i=1}^n\sum_{j=1}^n\operatorname{lcm}(a_i,a_j)
\]

\(1\le n,a_i\le5\times10^4\)。

\(\mathcal{Solution}\)

数论题在序列上搞不太现实，记最大值 \(m\)，有 \(c_i\) 个 \(a_j=i\)，推式子：

\[\begin{aligned}
\sum_{i=1}^n\sum_{j=1}^n\operatorname{lcm}(a_i,a_j)&=\sum_{i=1}^m\sum_{j=1}^m\frac{ij}{\gcd(i,j)}c_ic_j\\
&=\sum_{d=1}^m\sum_{i=1}^{\lfloor\frac{m}d\rfloor}\sum_{j=1}^{\lfloor\frac{m}d\rfloor}[\gcd(i,j)=1]dijc_ic_j\\
&=\sum_{d=1}^m\sum_{i=1}^{\lfloor\frac{m}d\rfloor}\sum_{j=1}^{\lfloor\frac{m}d\rfloor}dijc_ic_j\sum_{D|i\land D|j}\mu(D)~~~~(\text{Mobius 反演})\\
&=\sum_{d=1}^md\sum_{D=1}^{\lfloor\frac{m}d\rfloor}\mu(D)D^2\sum_{i=1}^{\lfloor\frac{m}{dD}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{dD}\rfloor}ijc_{idD}c_{jdD}~~~~(\text{交换枚举顺序})\\
&=\sum_{T=1}^mT\sum_{D|T}\mu(D)D\sum_{i=1}^{\lfloor\frac{m}T\rfloor}\sum_{j=1}^{\lfloor\frac{m}T\rfloor}ijc_{iT}c_{jT}~~~~(\text{改换枚举}~T=dD)\\
&=\sum_{T=1}^mT\left(\sum_{i=1}^{\lfloor\frac{m}T\rfloor}ic_{iT}\right)^2\sum_{D|T}\mu(D)D
\end{aligned}
\]

\(\mathcal O(n+m\sqrt m)\) 算就好啦。

\(\mathcal{Code}\)

#include <cmath>

#include <cstdio>

const int MAXN = 5e4;

int n, m, c[MAXN + 5];

int pn, pr[MAXN + 5], mu[MAXN + 5];

bool vis[MAXN + 5];

inline int rint () {

	int x = 0; char s = getchar ();

	for ( ; s < '0' || '9' < s; s = getchar () );

	for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );

	return x;

}

inline void sieve ( const int n ) {

	mu[1] = 1;

	for ( int i = 2; i <= n; ++ i ) {

		if ( !vis[i] ) mu[pr[++ pn] = i] = -1;

		for ( int j = 1, t; j <= pn && ( t = i * pr[j] ) <= n; ++ j ) {

			vis[t] = true;

			if ( !( i % pr[j] ) ) break;

			mu[t] = -mu[i];

		}

	}

}

int main () {

	n = rint ();

	for ( int i = 1, a; i <= n; ++ i ) {

		++ c[a = rint ()];

		if ( m < a ) m = a;

	}

	sieve ( m );

	long long ans = 0;

	for ( int i = 1; i <= m; ++ i ) {

		long long a = 0, b = 0;

		for ( int j = 1, t = m / i; j <= t; ++ j ) a += 1ll * j * c[i * j];

		for ( int j = 1, t = sqrt ( i ); j <= t; ++ j ) {

			if ( i % j ) continue;

			b += mu[j] * j;

			if ( j * j < i ) b += mu[i / j] * i / j;

		}

		ans += 1ll * i * a * a * b;

	}

	printf ( "%lld\n", ans );

	return 0;

}

\(\mathcal{Details}\)

推的时候把 \(ij\) 系数搞丢了自闭半天 qaq。

巴特西

Solution -「洛谷 P3911」最小公倍数之和

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

\(\mathcal{Details}\)

最新文章

热门文章