Numéricos - Implementações

Módulo

Entrada:

  • Inteiros a (podendo ser negativo!) e n > 0.

Saída:

  • Valor de a módulo n.

Complexidade: O( 1 )

Global:

int mod(int a, int n) {
return (a%n + n)%n;
}

Exponenciação Modular Rápida

Entrada:

  • Inteiros a, b e n.

Saída:

  • Valor de a^b mod n.

Complexidade: O( log(b) )

Global:

int expmod(int a, int b, int n) {
if(b == 0)
return 1;
else {
long long res = expmod(a, b/2, n);
res = (res*res) % n;
if(b%2 == 1)
res = (res*a) % n;
return (int) res;
}
}

Máximo Divisor Comum

Utiliza o algoritmo de Euclides.

Entrada:

  • Inteiros a e b.

Saída:

  • Maior inteiro que divide a e b.

Complexidade: O( log(a) + log(b) )

Global:

int mdc(int a, int b) {
if(a<0) a = -a;
if(b<0) b = -b;

if(b == 0)
return a;
else
return mdc(b, a%b);
}

Máximo Divisor Comum Estendido

Utiliza o algoritmo de Euclides estendido.

Entrada:

  • Inteiros positivos a e b.

Saída:

  • Maior inteiro que divide a e b como retorno.
  • Variáveis inteiras x e y tais que a.x + b.y = mdc(a,b).

Complexidade: O( log(a) + log(b) )

Global:

int mdc(int a, int b, int *x, int *y) {
int xx, yy, d;
if(b==0) {
*x=1; *y=0;
return a;
}

d = mdc(b, a%b, &xx, &yy);
*x = yy;
*y = xx - a/b*yy;
return d;
}

Teste de Primalidade

Entrada:

  • Inteiro n.

Saída:

  • Valor booleano que indica se n é primo ou não.

Complexidade: O( sqrt(n) )

Global:

int ehPrimo(int n) {
if(n==2) return 1;
if(n<=1 || n%2 == 0) return 0;

for(int i=3; i*i<=n; i+=2)
if(n%i == 0)
return 0;

return 1;
}

Crivo de Eratóstenes

Entrada:

  • Inteiro n <= MAXN.

Saída:

  • Vetor ehprimo[] que indica se os números menores ou iguais a n são primos ou não.

Complexidade: O( n.log(n) )

Global:

int ehprimo[MAXN+1];

void achaPrimos(int n) {
ehprimo[0] = ehprimo[1] = 0;
ehprimo[2] = 1;

for(int i=3; i<=n; i++)
ehprimo[i] = i%2;

for(int i=3; i*i<=n; i+=2)
if(ehprimo[i])
for(int j=i*i; j<=n; j+=i)
ehprimo[j] = 0;
}

Função 'phi' de Euler

Entrada:

  • Inteiro n > 0.

Saída:

  • Valor ϕ(n), onde ϕ é a função phi de Euler, equivalente ao número de primos relativos a n (mdc=1) menores o iguais a n.

Complexidade: O( n )

Dependências:

  • Crivo de Eratóstenes: ehprimo[i], para i <= n/2.

Global:

int phi(int n) {
int res = n;
for(int p=2; 2*p<=n; p++)
if(ehprimo[p] && n%p==0)
res = res/p*(p-1);
return res;
}

Resolvedor de Equação Modular Linear

Entrada:

  • Inteiro a e b quaiquer e n positivo.

Saída:

  • Menor valor positivo x tal que a.x == b (mod n) ou -1 se não houver solução.

Complexidade: O( n )

Dependências:

  • Módulo: mod(int a, int n).
  • MDC Estendido: mdc(int a,int b,int *x, int*y).

Global:

int solve(int a, int b, int n) {
int d, x, y;

a = mod(a, n);
b = mod(b, n);
d = mdc(a, n, &x, &y);
if(b%d==0)
return mod( ((long long)x%(n/d)) * ((b/d)%(n/d)) , n/d );
else
return -1;
}