Skip to Content
CTRL K

LCM Sum

Explicación

Usaremos la siguiente identidad para llevar la suma dada a una forma más conveniente:

x⋅y=gcd⁡(x,y)⋅lcm(x,y) x \cdot y=\gcd(x, y)\cdot\text{lcm}(x, y) ∑i=1nlcm(i,n)=∑i=1ni⋅ngcd⁡(i,n)=n⋅∑i=1nigcd⁡(i,n) \sum_{i = 1}^{n}{\texttt{lcm}(i, n)} = \sum_{i = 1}^{n}{\frac{i \cdot n}{\gcd(i, n)}}=n\cdot\sum_{i=1}^{n}{\frac{i}{\gcd(i, n)}}

Intentamos agrupar los términos por su valor. Sea d=gcd⁡(i,n)d=\gcd(i, n), entonces d∣nd|n:

n⋅∑i=1nigcd⁡(i,n)=n⋅∑d∣n∑i=1gcd(i,n)=dnid(1) n\cdot\sum_{i=1}^{n}{\frac{i}{\gcd(i, n)}}=n \cdot \sum_{d|n}\sum_{\substack{i=1\\gcd(i,n)=d}}^{n}{\frac{i}{d}} \tag{1}

Sea k=idk = \frac{i}{d} y m=ndm= \frac{n}{d}; de esto se obtiene que gcd⁡(k,m)=1\gcd(k, m)=1. Sustituyendo de vuelta en (1)(1) obtenemos:

n⋅∑d∣n∑k=1gcd(k,m)=1mk n\cdot\sum_{d|n}\sum_{\substack{k=1 \\ \text{gcd(k,m)=1}}}^{m}{k}

La suma interior es igual a m⋅ϕ(m)2\frac{m \cdot \phi(m)}{2} para m>1m > 1.

Implementación

Complejidad temporal: O(Nlog⁡N+T)\mathcal{O}(N\log{N} + T)

#include <iostream>
 
using namespace std;
 
const int MAXN = 1e6;
 
long long phi[MAXN + 1], sum[MAXN + 1];
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
 
	for (int i = 1; i <= MAXN; i++) { phi[i] = i; }
 
	for (int i = 2; i <= MAXN; i++) {
		// Si i es primo
		if (phi[i] == i) {
			for (int j = i; j <= MAXN; j += i) { phi[j] -= phi[j] / i; }
		}
	}
 
	for (int i = 1; i <= MAXN; i++) {
		for (int j = i; j <= MAXN; j += i) { sum[j] += i * phi[i]; }
	}
 
	int t;
	cin >> t;
 
	while (t--) {
		int n;
		cin >> n;
		long long ans = sum[n] + 1;
		ans = 1LL * ans * n / 2LL;
		cout << ans << '\n';
	}
 
	return 0;
}
Fundamentos