Aritmética modular

Introducción

En aritmética modular, en lugar de trabajar con los enteros mismos, trabajamos con sus restos al dividir por $m$. A esto lo llamamos tomar módulo $m$. Por ejemplo, si tomamos $m = 23$, entonces en lugar de trabajar con $x = 247$, usamos $x \bmod 23 = 17$. Por lo general, $m$ será un primo grande, dado en el problema; los dos valores más comunes son $10^9 + 7$ y $998\,244\,353=119\cdot 2^{23}+1$. La aritmética modular se usa para evitar tratar con números que desbordan los tipos de datos nativos, porque podemos tomar restos, de acuerdo con las siguientes fórmulas:

Exponenciación modular

Recursos

La exponenciación binaria se puede usar para calcular de forma eficiente $x ^ n \mod m$. Para ello, descompongamos $x ^ n$ en componentes binarios. Por ejemplo, $5 ^ {10}$ = $5 ^ {1010_2}$ = $5 ^ 8 \cdot 5 ^ 2$. Entonces, si conocemos $x ^ y$ para todo $y$ que es potencia de dos ($x ^ 1$, $x ^ 2$, $x ^ 4$, $\dots$ , $x ^ {2^{\lfloor{\log_2n} \rfloor}}$, podemos calcular $x ^ n$ en $\mathcal{O}(\log n)$.

Para tratar con $m$, observemos que el módulo no afecta las multiplicaciones, así que podemos implementar directamente el algoritmo de “exponenciación binaria” de arriba añadiendo una línea para tomar los resultados $\pmod m$.

Solución - Exponentiation

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
ll exp(ll x, ll n, ll m) {
	assert(n >= 0);
	x %= m;  // note: m * m must be less than 2^63 to avoid ll overflow
	ll res = 1;
	while (n > 0) {
		if (n % 2 == 1) { res = res * x % m; }
		x = x * x % m;
		n /= 2;
	}
	return res;
}
 
int main() {
	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		int a, b;
		cin >> a >> b;
		cout << exp(a, b, 1e9 + 7) << "\n";
	}
}

import java.io.*;
import java.util.*;
 
public class Exponentiation {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		int n = Integer.parseInt(br.readLine());
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			long a = Long.parseLong(st.nextToken());
			long b = Long.parseLong(st.nextToken());
			out.println(exp(a, b, (long)1e9 + 7));
		}
		out.close();
	}
 
	public static long exp(long x, long n, long m) {
		assert (n >= 0);
		x %= m;  // note: m * m must be less than 2^63 to avoid ll overflow
		long res = 1;
		while (n > 0) {
			if (n % 2 == 1) { res = res * x % m; }
			x = x * x % m;
			n /= 2;
		}
		return res;
	}
}

MOD = 10**9 + 7
 
for _ in range(int(input())):
	first, second = [int(i) for i in input().split()]
	print(pow(first, second, MOD))

Inverso modular

El inverso modular es el equivalente del recíproco en la aritmética de números reales; para dividir $a$ por $b$, se multiplica $a$ por el inverso modular de $b$. Aquí solo consideraremos módulos primos $p$.

Por ejemplo, el inverso de $2$ módulo $p=10^9+7$ es $i=\frac{p+1}{2}=5\cdot 10^8+4$. Esto significa que para cualquier entero $x$,

Por ejemplo, $10i\equiv 5\pmod{10^9+7}$.

Con exponenciación

El pequeño teorema de Fermat (no confundir con el último teorema de Fermat) afirma que todos los enteros $a$ no divisibles por $p$ satisfacen $a^{p - 1} \equiv 1 \pmod{p}$. En consecuencia, $a^{p-2} \cdot a \equiv 1 \pmod{p}$. Por lo tanto, $a^{p - 2}$ es un inverso modular de $a$ módulo $p$.

const int MOD = 1e9 + 7;
 
int main() {
	ll x = exp(2, MOD - 2, MOD);
	cout << x << "\n";  // 500000004
	assert(2 * x % MOD == 1);
}

public class Main {
	public static final int MOD = (int)Math.pow(10, 9) + 7;
	public static void main(String[] args) throws IOException {
		long x = exp(2, MOD - 2, MOD);
		System.out.println(x);  // 500000004
		assert (2 * x % MOD == 1);
	}
}

MOD = 10**9 + 7
 
x = pow(2, MOD - 2, MOD)
print(x)  # 500000004
assert 2 * x % MOD == 1

Con división euclidiana

También podemos hallar inversos modulares mediante la división euclidiana. Dado el módulo primo $m > a$ tenemos:

donde $k = \lfloor \frac{m}{a} \rfloor$ y $r = m \mod a$. Entonces:

Aquí hay una implementación recursiva breve de la fórmula anterior:

int inv(int x) { return x <= 1 ? x : MOD - MOD / x * inv(MOD % x) % MOD; }

static int inv(int x) {
	return x <= 1 ? x : MOD - MOD / x * inv(MOD % x) % MOD;
}

def inv(x: int) -> int:
	return x if x <= 1 else MOD - MOD // x * inv(MOD % x) % MOD

La ventaja de este enfoque es que podemos precomputar el inverso modular de los números en el rango $[1, MOD)$ en $\mathcal{O}(MOD)$.

inv[1] = 1;  // assume we already defined this array
for (int i = 2; i < MOD; i++) { inv[i] = MOD - MOD / i * inv[MOD % i] % MOD; }

inv[1] = 1;  // assume we already defined this array
for (int i = 2; i < MOD; i++) { inv[i] = MOD - MOD / i * inv[MOD % i] % MOD; }

inv[1] = 1  # assume we already defined this array
for i in range(2, MOD):
	inv[i] = MOD - MOD / i * inv[MOD % i] % MOD

Como toma $\mathcal{O}(\log p)$ tiempo calcular un inverso modular módulo $p$, el uso frecuente de la división dentro de un bucle puede aumentar de forma significativa el tiempo de ejecución de un programa. Si el inverso modular del mismo número (o de los mismos números) se usa muchas veces, es buena idea precalcularlo.

Además, siempre hay que asegurarse de no intentar dividir por 0. Tener en cuenta que después de aplicar el módulo, un número distinto de cero puede volverse cero, así que hay que tener mucho cuidado al dividir por valores no constantes.

#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1e9 + 7;
 
// BeginCodeSnip{ModInt}
struct mi {
	int v;
	explicit operator int() const { return v; }
	mi() { v = 0; }
	mi(long long _v) : v(_v % MOD) { v += (v < 0) * MOD; }
};
mi &operator+=(mi &a, mi b) {
	if ((a.v += b.v) >= MOD) a.v -= MOD;
	return a;
}
mi &operator-=(mi &a, mi b) {
	if ((a.v -= b.v) < 0) a.v += MOD;
	return a;
}
mi operator+(mi a, mi b) { return a += b; }
mi operator-(mi a, mi b) { return a -= b; }
mi operator*(mi a, mi b) { return mi((long long)a.v * b.v); }
mi &operator*=(mi &a, mi b) { return a = a * b; }
mi pow(mi a, long long p) {
	assert(p >= 0);
	return p == 0 ? 1 : pow(a * a, p / 2) * (p & 1 ? a : 1);
}
mi inv(mi a) {
	assert(a.v != 0);
	return pow(a, MOD - 2);
}
mi operator/(mi a, mi b) { return a * inv(b); }
// EndCodeSnip
 
int main() {
	{
		int a = 1e8, b = 1e8, c = 1e8;
		cout << (long long)a * b % MOD * c % MOD << "\n";  // 49000000
	}
	{
		mi a = 1e8, b = 1e8, c = 1e8;
		// cout << a * b * c << "\n";  // Errors- we have to cast this an an int
		cout << (int)(a * b * c) << "\n";  // 49000000
	}
}

#include <bits/stdc++.h>
using namespace std;
 
// https://atcoder.github.io/ac-library/document_en/modint.html
// (included in atcoder grading)
#include <atcoder/modint>
using mint = atcoder::modint;
 
const int MOD = 1e9 + 7;
 
int main() {
	// Set a global modulus
	mint::set_mod(MOD);
 
	// Scientific notation doesn't work with AtCoder's class
	mint a = 100000000;
	mint b = 100000000;
	mint c = 100000000;
 
	mint res = a * b * c;
	cout << res.val() << endl;  // Same result
}

Problemas