수학

나머지 연산

• (A+B) mod M = ((A mod M) + B mod M) mod M
• (AB) mod M = ((a mod M) (B mod M)) mod M
• 뺄셈의 경우에는 먼저 mod 연산을 한 결과가 음수로 나올 수 있기 때문에 다음과 같이 해야한다.
• (A-B) mod M = ((a mod M) - ( B mod M) + M) mod M
• 단, 나누기의 경우에는 성립하지 않는다.

최대공약수

• GCD(Greatest Common Divisor)
• 두 수 A와 B의 최대공약수 G는 A와 B의 공통된 약수 중에서 가장 큰 정수이다.
• 최대공약수가 1인 두 수를 서로소(Coprime)라고 한다.
• O(N) (N=, max(a, b))

int g = 1;
for(int i=2; i<min(a,b); i++){
  if(a % i == 0 && b % i == 0){
    g = i;
  }
}

• 유클리드 호제법을 이용하면 더 빨라짐.
  • a를 b로 나눈 나머지를 r이라고 했을 때,
  • GCD(a, b) = GCD(b, r)과 같다.
  • r이 0이면 그 때 b가 최대 공약수이다.
  • GCD(24, 16) = GCD(16, 8) = GCD(8, 0) = 8
• 재귀함수를 사용해서 구현한 유클리드 호제법

int gcd(int a, int b){
	if (b == 0){
    return a;
  } else {
    return gcd(b, a%b);
  }
}

• 재귀함수를 사용하지 않고 구현한 유클리드 호제법
• O(lg N)

int gcd(int a, int b){
  while(b != 0){
    int r = a%b;
    a = b;
    b = r;
  }
  return a;
}

최소 공배수

• LCM(Least Common Multiple)
• 두 수의 최소공배수는 두 수의 공통된 배수 중에서 가장 작은 정수
• 두 수 a, b의 최대공약수를 g라고 했을 때,
• 최소공배수 l = g (a/g) (b/g)

소수

• 소수: 약수가 1과 자기 자신 밖에 없는 수
• 2보다 크거나 같고, N-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

• 소수와 관련된 알고리즘.
  • 어떤 수 N이 소수인지 아닌지 판별하는 방법.
  • N보다 작거나 같은 모든 자연수 중에서 소수를 찾아내는 방법.

bool prime(int n){
  if(n < 2){
    return false;
  }
  for(int i=2; i<=n-1; i++){
    if (n%i==0){
      return false;
    }
  }
  return true;
}

• N이 소수가 되려면, 2보다 크거나 같고, N/2보다 작거나 같은 자연수로 나누어 떨어지면 안된다.
  • 이유: N의 약수 중에서 가장 큰 것은 N/2보다 작거나 같기 때문
  • N = a * b로 나타낼 수 있는데, a가 작을수록 b는 크다.
  • 가능한 a 중에서 가장 작은 값은 2이기 때문에, b는 N/2를 넘지 않는다.

bool prime(int n){
  if (n<2){
    return false;
  }
  for(int i=2; i<=n/2; i++){
    if(n%i == 0){
      return false;
    }
  }
  return true;
}

• N이 소수가 되려면, 2보다 크거나 같고, 루트 N보다 작거나 같은 자연수로 나누어 떨어지면안된다.
  • 이유: N이 소수가 아니라면, N = a * b로 나타낼 수 있다. (a <= b)
  • a>b라면, 두 수를 바꿔서 항상 a<=b로 만들 수 있다.
  • 두 수 a와 b의 차이가 가장 작은 경우는 루트 N이다.
  • 따라서, 루트 N까지만 검사를 해보면 된다.
  • O(루트N)

bool prime(int n){
  if (n<2){
    return false;
  }
  //실수표현은 잘 쓰지않음.
  //근사값으로 나오기 때문.
  //i <= rt N 대신, i*i<=N이라 씀
  for(int i=2; i*i<=n; i++){
    if (n%i == 0){
      return fales;
    }
  }
  return true;
}

에라토스테네스의 체

• 지워지지 않은 수 중에서 가장 작은 수는 2이다.
• 2는 소수이고, 2의 배수는 모두 지운다.

int prime[100]; // 소수 저장
int pn=0; // 소수의 개수
bool check[101]; // 지워졌으면 true
int n=100; // 100까지의 소수
for(int i=2; i<=n; i++){
  if (check[i]false){
    prime[pn++] = i;
    //평소에는 i*i보다 i*2쓰는 것을 권장.
    //i=백만인 경우, i*i는 범위를 넘어가기 때문.
    for(int j=i*i; j<=n; j+=i){
      check[j] = true;
    }
  }
}

골드바흐의 추측

• 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다.
• 위의 문장에 3을 더하면
• 5보다 큰 모든 호루는 세 소수의 합으로 표현 가능하다로 바뀐다
• 이는 아직 증명되지 않은 문제로, 10의 18승 이하에서는 참인 것이 증명되어 있다.

다른 추측

• 6 이상의 모든 소수는 6n+1 또는 6n+5로 표현될 수 있다.
  • 6n+2: 2의 배수
  • 6n+3: 3의 배수
  • 6n+4: 2의 배수

팩토리얼

• 팩토리얼은 매우 큰 값.

팩토리얼 0의 개수

• N!의 0이 몇 개인지 알아내려면, N!을 소인수분해 했을 때, 2와 5가 몇개 나오는지 알아야한다.
• 5의 개수가 항상 2의 개수보다 적기 때문에, 5의 개수만 세어주면 된다.
• N! 0의 개수 = [N/5] + [N/5^2] + [N/5^3] + ...
• 100!의 경우 인수로 5가 들어가있는 것을 찾아보자.
  • 100 / 5 = 20.
• 100!의 경우로 인수가 5^2가 들어가는 것을 찾아보자.
  • 100 / 5^2 = 4.

조합 0의 개수

• nCm의 0의 개수를 구하는 문제
• 예외가 있을 수 있음. 그래서 2와 5의 경우를 각각 해보고, 최솟값을 기준으로 구하면 됨.