Sobre

Computa o inverso de a modulo b

Se b eh primo, basta fazer

a^(b-2)

Link original: modInverse.cpp

Código 

  ll inv(ll a, ll b) {
	return a > 1 ? b - inv(b%a, a)*b/a : 1;
}

// computa o inverso modular de 1..MAX-1 modulo um primo
ll inv[MAX]:
inv[1] = 1;
for (int i = 2; i < MAX; i++) inv[i] = MOD - MOD/i*inv[MOD%i]%MOD;