Multiple of 2019

Análisis oficial 

Explicación

Para guardar secciones del string, podemos construir un arreglo de sufijos $S$ tal que:

Por ejemplo, si nuestro string fuera $$1234$$ y el módulo fuera $$3$$ (en lugar de $$2019$$, por simplicidad), el arreglo de sufijos sería

Hay que tener en cuenta que también se considera un sufijo vacío.

Esto es útil porque podemos acceder a cualquier subcadena en $\mathcal{O}(1)$ mediante una consulta de rango. Así, si $${S_0} = 1234$$ y $${S_3=4}$$, esto significa $${S_0}-{S_3} = 123 * {10^1}$$ o $$1230$$.

También significa que si tanto $${S_0}(mod$$ $$M)=$$ $${S_3}(mod$$ $$M)$$ (ambos sufijos tienen el mismo resto), restar llevaría a $${S_0}(mod$$ $$M)-$$ $${S_3}(mod$$ $$M)=0$$, es decir, una subcadena divisible por $$2019$$.

Así, con $$1234$$, $${S_0-{S_3}=1234(mod}$$ $$3)-4(mod$$ $$3)=1-1=0$$. Como restan a cero, la subcadena del índice $$0$$ al $$2$$ da un número divisible por el módulo. (La subcadena es $$123$$, que es divisible por 3).

Sin embargo, todavía tendríamos que recorrer cada par de sufijos posibles $(i, j)$, lo que sería $\mathcal{O}(N^2)$.

En su lugar, no necesitamos saber qué sufijo tiene un cierto resto, sino cuántos sufijos tienen ese resto.

Para detallar, podemos tomar $${N \choose K}$$ y elegir 2 números divisibles por el mismo resto de 2019, donde $$N=$$ la cantidad de veces que ocurre un cierto resto, y $$K=$$ 2 (porque elegimos 2 índices $$i$$ y $$j$$).

Por lo tanto, nuestra respuesta es el conteo de todos los restos en un arreglo de $$0...2018$$ y $${N \choose 2}$$.

Así, en nuestro ejemplo con $$1234$$, el nuevo arreglo se vería así:

Donde cada índice representa el conteo de un cierto resto.

• Hay $$2$$ sufijos con resto $$0$$ al dividir por $$3$$, $$[234, 0]$$
• Hay $$3$$ sufijos con resto $$1$$ al dividir por $$3$$, $$[1234, 34, 4]$$
• Y no hay sufijos con resto $$2$$

Entonces, la suma de todos estos números sería $${2 \choose 2} + {3 \choose 2}=1+3=4$$

Si $$N<K$$, debería ser $$0$$, porque no hay sufijos suficientes para formar un par.

Video de Errichto

Video de YouTube (83yW2Pp6HMk)

Implementación

Complejidad temporal: $\mathcal{O}(N)$

#include <iostream>
using namespace std;
 
int main() {
	string s;
	cin >> s;
	int num = 0, n = s.size(), pow = 1;
	// inicializa el arreglo con initializer list
	// explicado aquí: https://www.learncpp.com/cpp-tutorial/arrays-part-ii/
	int count[2019]{1};
	for (int i = n - 1; i >= 0; i--) {
		// hallamos el resto del número actual módulo 2019
		num = (num + pow * (s[i] - '0')) % 2019;
		// incrementamos el conteo de este resto
		count[num]++;
		pow = pow * 10 % 2019;
	}
	long long ans = 0;
	for (int i = 0; i < 2019; i++) {
		// hay nC2 formas de emparejar los números con el mismo resto
		ans += (long long)count[i] * (count[i] - 1) / 2;
	}
	cout << ans << endl;
	return 0;
}

import java.io.*;
import java.util.*;
 
public class MultipleOf2019 {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		String numberString = io.next();
		int num = 0;
		int stringLength = numberString.length();
		int pow = 1;
		int[] count = new int[2019];
		count[0] = 1;
 
		for (int i = stringLength - 1; i >= 0; i--) {
			// hallamos el resto del número actual módulo 2019
			num = (num + pow * (numberString.charAt(i) - '0')) % 2019;
			// incrementamos el conteo de este resto
			count[num]++;
			pow = pow * 10 % 2019;
		}
		long answer = 0;
		for (int i = 0; i < 2019; i++) {
			// hay nC2 formas de emparejar los números con el mismo resto
			answer += (long)count[i] * (count[i] - 1) / 2;
		}
		io.println(answer);
		io.close();
	}
	// CodeSnip{Kattio}
}

MOD = 2019
string = input()
 
count = [0] * MOD
count[0] = 1
 
cur_num = 0
power = 1
for c in reversed(string):
	# hallamos el resto del número actual MOD 2019
	cur_num = (int(c) * power + cur_num) % MOD
	# aumentamos la potencia de 10
	power = (power * 10) % MOD
	# aumentamos el conteo de este resto
	count[cur_num] += 1
 
ans = 0
for rep in count:
	# cuando el resto i se repite rep veces hay C(rep, 2) pares válidos
	ans += (rep * (rep - 1)) // 2
print(ans)