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;

}