Be Geeks! (Editorial)

El número de pares $(i, j)$ es igual a $n \cdot (n + 1) /2$ n \cdot (n + 1) / 2, y para $n = 2 \cdot 1 0^{5}$ n = 2 \cdot 10^5 es aproximadamente $2 \cdot 1 0^{10}$ 2 \cdot 10^{10}, por lo que enumerar todos los segmentos es imposible. Calcularemos la suma mediante el método "divide y vencerás", dividiendo el arreglo en la posición del elemento máximo.

División en el máximo. Supongamos que necesitamos hallar la suma de $P (i, j)$ P(i, j) sobre todos los segmentos $[i; j]$ contenidos en el segmento $[b; e]$ . Hallemos la posición $m$ del elemento máximo en $[b; e]$ . Cada segmento $[i; j] \subseteq [b; e]$ [i; j] \subseteq [b; e] pertenece exactamente a uno de tres tipos:

contiene la posición $m$ , es decir, $b \leq i \leq m \leq j \leq e$ b \le i \le m \le j \le e;
está contenido por completo en $[b; m - 1]$ [b; m - 1];
está contenido por completo en $[m + 1; e]$ [m + 1; e].

Los segmentos del segundo y del tercer tipo se procesan recursivamente. Para los segmentos del primer tipo el máximo es igual a $a_{m}$ a_m, por lo que $M (i, j) = a_{m}$ M(i, j) = a_m, y su contribución total es igual a

a_{m} \cdot \sum G (i, j), donde la suma se toma sobre todos los b \leq i \leq m \leq j \leq e

a_m \cdot \sum G(i, j), \quad \text{donde la suma se toma sobre todos los } b \le i \le m \le j \le e

Queda calcular rápidamente la suma de los MCD sobre todos los segmentos que contienen la posición $m$ .

Descomposición del MCD. Un segmento $[i; j]$ que contiene a $m$ está formado por la parte izquierda $[i; m]$ y la parte derecha $[m; j]$ . Por lo tanto

G (i, j) = g cd (G (i, m), G (m, j))

G(i, j) = \gcd\bigl(G(i, m), G(m, j)\bigr)

Así, el MCD de un segmento queda determinado por un par de valores: el MCD de la parte izquierda y el MCD de la parte derecha.

Grupos de extremos. A medida que $j$ aumenta, el valor $G (m, j)$ G(m, j) no aumenta. Además, cada vez que cambia, el nuevo valor es un divisor propio del anterior y, por lo tanto, es al menos dos veces menor. En consecuencia, $G (m, j)$ G(m, j) toma como máximo $⌊ lo g_{2} C ⌋ + 1$ \lfloor \log_2 C \rfloor + 1 valores distintos, donde $C$ es el mayor valor de un elemento. Para $C \leq 1 0^{9}$ C \le 10^9 esto son como máximo $⌊ lo g_{2} C ⌋ + 1 = 30$ \lfloor \log_2 C \rfloor + 1 = 30 valores.

Las posiciones $j$ con el mismo valor de $G (m, j)$ G(m, j) forman un bloque contiguo. Llamaremos a un bloque de posiciones así grupo. Cada grupo se describe mediante un par $(g, cnt)$ (g, \mathit{cnt}), donde $g$ es el valor del MCD y $cnt$ es el número de posiciones del grupo. De manera análoga, los extremos izquierdos $i$ se dividen en grupos según el valor de $G (i, m)$ .

El final de un grupo se encuentra mediante búsqueda binaria. Si un grupo empieza en la posición $j$ y $g = G (m, j)$ g = G(m, j), entonces la igualdad $G (m, t) = g$ G(m, t) = g se cumple para todos los $t$ desde $j$ hasta el final del grupo y no se cumple para ningún $t$ posterior.

Suma sobre pares de grupos. Sea $(g_{L}, cnt_{L})$ (g_L, \mathit{cnt}_L) el grupo izquierdo y $(g_{R}, cnt_{R})$ (g_R, \mathit{cnt}_R) el grupo derecho. Entonces todos los $cnt_{L} \cdot cnt_{R}$ \mathit{cnt}_L \cdot \mathit{cnt}_R segmentos cuyo extremo izquierdo está en el grupo izquierdo y cuyo extremo derecho está en el grupo derecho tienen el mismo MCD $g cd (g_{L}, g_{R})$ \gcd(g_L, g_R). Por lo tanto

\sum G (i, j) = \sum g cd (g_{L}, g_{R}) \cdot cnt_{L} \cdot cnt_{R},

\sum G(i, j) = \sum \gcd(g_L, g_R) \cdot \mathit{cnt}_L \cdot \mathit{cnt}_R,

donde la segunda suma se toma sobre todos los pares formados por un grupo izquierdo y un grupo derecho. El número de tales pares no supera $30 \cdot 30$ 30 \cdot 30.

Consultas en rangos. Para hallar la posición del máximo y calcular el MCD en un segmento, usamos dos tablas dispersas (Sparse Table). Ambas operaciones son idempotentes: $max (x, x) = x$ \max(x, x) = x y $g cd (x, x) = x$ \gcd(x, x) = x. Por lo tanto, una consulta en un rango se responde usando dos bloques superpuestos de longitud $2^{k}$ 2^k.

El valor de $F (A)$ es muy grande, por lo que todos los cálculos se realizan módulo $1 0^{9} + 7$ 10^9 + 7.

Complejidad. Cada llamada recursiva excluye una posición $m$ , por lo que hay como máximo $n$ llamadas. En cada llamada hay como máximo $O (lo g C)$ O(\log C) grupos a cada lado. El final de un grupo se encuentra mediante búsqueda binaria con $O (lo g n)$ O(\log n) consultas de MCD, y cada consulta requiere $O (lo g C)$ O(\log C). Recorrer los pares de grupos requiere $O (lo g^{2} C)$ O(\log^2 C) cálculos de MCD. La construcción de las tablas dispersas requiere $O (n lo g n \cdot lo g C)$ O(n \log n \cdot \log C). La complejidad total es $O (n lo g^{2} C \cdot (lo g n + lo g C))$ O(n \log^2 C \cdot (\log n + \log C)). En la práctica hay muchos menos de $30$ grupos y el algoritmo funciona rápidamente.

Ejemplo

Consideremos el segundo ejemplo: $A = (2, 4, 6, 12, 3)$ A = (2, 4, 6, 12, 3). Las posiciones se numeran a partir de uno.

La primera llamada procesa todo el arreglo $[1; 5]$ . El elemento máximo es $a_{4} = 12$ a_4 = 12, por lo que $m = 4$ m = 4. La figura muestra los grupos de extremos izquierdos y derechos.

Extremos izquierdos: $G (4, 4) = 12$ G(4, 4) = 12, $G (3, 4) = g cd (6, 12) = 6$ G(3, 4) = \gcd(6, 12) = 6, $G (2, 4) = G (1, 4) = 2$ G(2, 4) = G(1, 4) = 2. Obtenemos los grupos $(12, 1)$ , $(6, 1)$ y $(2, 2)$ .

Extremos derechos: $G (4, 4) = 12$ G(4, 4) = 12, $G (4, 5) = g cd (12, 3) = 3$ G(4, 5) = \gcd(12, 3) = 3. Obtenemos los grupos $(12, 1)$ y $(3, 1)$ .

Recorramos todos los pares de grupos:

grupo izquierdo	grupo derecho	MCD	segmentos	contribución
(12, 1)	(12, 1)	12	1	12
(12, 1)	(3, 1)	3	1	3
(6, 1)	(12, 1)	6	1	6
(6, 1)	(3, 1)	3	1	3
(2, 2)	(12, 1)	2	2	4
(2, 2)	(3, 1)	1	2	2

La suma de los MCD sobre los segmentos que contienen la posición $4$ es $12 + 3 + 6 + 3 + 4 + 2 = 30$ 12 + 3 + 6 + 3 + 4 + 2 = 30, y la contribución de estos segmentos es $12 \cdot 30 = 360$ 12 \cdot 30 = 360. Por ejemplo, la última fila de la tabla corresponde a los segmentos $[1; 5]$ y $[2; 5]$ : para cada uno de ellos el MCD es 1 y el máximo es 12.

A continuación se procesan recursivamente los segmentos $[1; 3]$ y $[5; 5]$ . Todas las llamadas se muestran en la tabla:

segmento	$m$	$a_{m}$ \boldsymbol{a_m}	grupos izquierdos	grupos derechos	suma de MCD	contribución
$[1; 5]$ \boldsymbol{[1; 5]}	4	12	(12, 1), (6, 1), (2, 2)	(12, 1), (3, 1)	30	360
$[1; 3]$ \boldsymbol{[1; 3]}	3	6	(6, 1), (2, 2)	(6, 1)	10	60
$[1; 2]$ \boldsymbol{[1; 2]}	2	4	(4, 1), (2, 1)	(4, 1)	6	24
$[1; 1]$ \boldsymbol{[1; 1]}	1	2	(2, 1)	(2, 1)	2	4
$[5; 5]$ \boldsymbol{[5; 5]}	5	3	(3, 1)	(3, 1)	3	9

La respuesta es $360 + 60 + 24 + 4 + 9 = 457$ 360 + 60 + 24 + 4 + 9 = 457.

Implementación del algoritmo

Declaramos las constantes:

$MOD = 1 0^{9} + 7$ \mathit{MOD} = 10^9 + 7 — el módulo,
$LOG = 18$ \mathit{LOG} = 18 — el mayor exponente en las tablas dispersas ( $2^{18} > 2 \cdot 1 0^{5}$ 2^{18} > 2 \cdot 10^5).

Declaramos el tipo ll.

#define MOD 1000000007LL
#define LOG 18 // 2^18 = 262144 > 2*10^5
typedef long long ll;

La secuencia se almacena en el arreglo $a$ ; los elementos se indexan desde cero. El valor $lg2 [len]$ es igual a $⌊ lo g_{2} len ⌋$ \lfloor \log_2 \mathit{len} \rfloor. La tabla dispersa $spMax [i] [k]$ \mathit{spMax}[i][k] almacena el índice del elemento máximo, y $spGcd [i] [k]$ \mathit{spGcd}[i][k] almacena el MCD de los elementos del segmento $[i; i + 2^{k} - 1]$ [i; i + 2^k - 1].

vector<int> a;
vector<int> lg2;          // lg2[len] = floor(log2(len))
// spMax[i][k] — índice del máximo en [i, i + 2^k)
vector<vector<int>> spMax;
// spGcd[i][k] — MCD en [i, i + 2^k)
vector<vector<int>> spGcd;

La función gcd calcula el MCD de dos números mediante el algoritmo de Euclides.

int gcd(int x, int y)
{
  while (y) { int t = x % y; x = y; y = t; }
  return x;
}

La función better, dados dos índices $i$ y $j$ , devuelve aquel cuyo elemento del arreglo es mayor. Si los elementos son iguales, devuelve $i$ .

int better(int i, int j)
{
  return a[i] >= a[j] ? i : j;
}

La función build rellena el arreglo $lg2$ y construye ambas tablas dispersas en $O (n lo g n \cdot lo g C)$ O(n \log n \cdot \log C), $C \leq 1 0^{9}$ C \le 10^9.

void build()
{
  lg2.assign(n + 1, 0);
  for (int len = 2; len <= n; len++) lg2[len] = lg2[len / 2] + 1;
  spMax.assign(n, vector<int>(LOG + 1));
  spGcd.assign(n, vector<int>(LOG + 1));
  for (int i = 0; i < n; i++)
  {
    spMax[i][0] = i;
    spGcd[i][0] = a[i];
  }
  for (int k = 1; (1 << k) <= n; k++)
    for (int i = 0; i + (1 << k) <= n; i++)
    {
      int h = 1 << (k - 1);    // mitad de la longitud del bloque
      spMax[i][k] = better(spMax[i][k - 1], spMax[i + h][k - 1]);
      spGcd[i][k] = gcd(spGcd[i][k - 1], spGcd[i + h][k - 1]);
    }
}

C++

La función qMax devuelve el índice del elemento máximo en el segmento $[l; r]$ [l; r].

int qMax(int l, int r)
{
  int k = lg2[r - l + 1];
  return better(spMax[l][k], spMax[r - (1 << k) + 1][k]);
}

La función qGcd devuelve el MCD de los elementos del segmento $[l; r]$ [l; r]. Los bloques de longitud $2^{k}$ 2^k pueden superponerse, pero esto no afecta al resultado, ya que $g cd (x, x) = x$ \gcd(x, x) = x.

int qGcd(int l, int r)
{
  int k = lg2[r - l + 1];
  return gcd(spGcd[l][k], spGcd[r - (1 << k) + 1][k]);
}

La función lastRight encuentra la posición más a la derecha $t \in [from; e]$ t \in [\mathit{from}; e] tal que $G (m, t) = g$ G(m, t) = g. Aquí $g = G (m, from)$ g = G(m, \mathit{from}). Como $G (m, t)$ no aumenta al crecer $t$ , la igualdad se cumple en una parte inicial del segmento $[from; e]$ , y la búsqueda binaria encuentra su última posición. El punto medio se calcula como $(lo + hi + 1) /2$ (\mathit{lo} + \mathit{hi} + 1) / 2 para que la búsqueda no se quede atascada en la asignación $lo = mid$ \mathit{lo} = \mathit{mid}.

int lastRight(int m, int from, int e, int g)
{
  int lo = from, hi = e;
  while (lo < hi)
  {
    int mid = (lo + hi + 1) / 2;
    if (qGcd(m, mid) == g) lo = mid; else hi = mid - 1;
  }
  return lo;
}

C++

La función firstLeft encuentra de forma simétrica la posición más a la izquierda $t \in [b; from]$ t \in [b; \mathit{from}] tal que $G (t, m) = g$ G(t, m) = g.

int firstLeft(int m, int from, int b, int g)
{
  int lo = b, hi = from;
  while (lo < hi)
  {
    int mid = (lo + hi) / 2;
    if (qGcd(mid, m) == g) hi = mid; else lo = mid + 1;
  }
  return lo;
}

C++

La estructura Group describe un grupo de extremos de segmentos:

$g$ — el valor del MCD,
$cnt$ — el número de posiciones del grupo.

struct Group { int g; ll cnt; };

La función solve devuelve, módulo $MOD$ , la suma de $P (i, j)$ P(i, j) sobre todos los segmentos $[i; j]$ contenidos en $[b; e]$ . Para un segmento vacío la suma es $0$ .

ll solve(int b, int e)
{
  if (b > e) return 0;

Hallamos la posición $m$ del elemento máximo en $[b; e]$ .

  int m = qMax(b, e);

Dividimos los extremos derechos $j = m, m + 1, \dots, e$ j = m, m + 1, \ldots, e en grupos. Para el $j$ actual calculamos $g = G (m, j)$ g = G(m, j) y con la función lastRight encontramos la última posición $t$ del grupo. El grupo contiene $t - j + 1$ t - j + 1 posiciones; el siguiente grupo empieza en la posición $t + 1$ t + 1.

  vector<Group> R;
  for (int j = m; j <= e; )
  {
    int g = qGcd(m, j);
    int t = lastRight(m, j, e, g);
    R.push_back({ g, t - j + 1 });
    j = t + 1;
  }

C++

De manera análoga, dividimos en grupos los extremos izquierdos $i = m, m - 1, \dots, b$ i = m, m - 1, \ldots, b. El grupo ocupa las posiciones de $t$ a $i$ y contiene $i - t + 1$ i - t + 1 posiciones; el siguiente grupo termina en la posición $t - 1$ t - 1.

  vector<Group> L;
  for (int i = m; i >= b; )
  {
    int g = qGcd(i, m);
    int t = firstLeft(m, i, b, g);
    L.push_back({ g, i - t + 1 });
    i = t - 1;
  }

C++

Calculamos la suma $sumG$ de los valores del MCD sobre todos los segmentos que contienen la posición $m$ . Para cada par de grupos sumamos $g cd (l . g, r . g) \cdot l . cnt \cdot r . cnt$ \gcd(l.g, r.g) \cdot l.\mathit{cnt} \cdot r.\mathit{cnt}. El producto $l . cnt \cdot r . cnt$ l.\mathit{cnt} \cdot r.\mathit{cnt} no supera $4 \cdot 1 0^{10}$ 4 \cdot 10^{10} y cabe en el tipo long long. Lo reducimos módulo $MOD$ ; después de eso, el producto del MCD (menor que $2^{30}$ 2^{30}) por un número menor que $MOD$ también cabe en long long.

  ll sumG = 0;
  for (Group &l : L)
    for (Group &r : R)
    {
      ll cnt = (l.cnt * r.cnt) % MOD;
      sumG = (sumG + gcd(l.g, r.g) % MOD * cnt) % MOD;
    }

C++

El máximo en todos los segmentos que contienen a $m$ es igual a $a_{m}$ a_m, por lo que su contribución total es igual a $a_{m} \cdot sumG$ a_m \cdot \mathit{sumG}.

  ll res = (ll)a[m] % MOD * sumG % MOD;

Sumamos las sumas calculadas recursivamente para los segmentos situados por completo a la izquierda y a la derecha de la posición $m$ .

  return (res + solve(b, m - 1) + solve(m + 1, e)) % MOD;
}

Parte principal del programa. Leemos los datos de entrada.

scanf("%d", &n);
a.resize(n);
for (int &x : a) scanf("%d", &x);

Construimos las tablas dispersas.

build();

Imprimimos la respuesta para todo el arreglo — el segmento $[0; n - 1]$ [0; n - 1].

printf("%lld\n", solve(0, n - 1));