math

나머지 연산

(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)

두 수의 공통된 약수 중 가장 큰 정수

가장 간단하게 구하는 방법: 2부터 min(A, B)까지 모든 정수로 나누어 보기 (O(N)의 시간복잡도)

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가 최대공약수

//재귀함수 사용한 방법
//a < b라고 해서 a, b를 swap 시킬 필요없음
 int gcd(int a, int b) {
     if(b == 0) {
         return b;
     }
     else {
         return gcd(b, a%b);
     }
 }

 //반복문을 사용한 방법
 //O(lgN)의 시간복잡도
 int gcd(int a, int b) {
     while(b != 0) {
         int r = a%b;
         a = b;
         b = r;
     }
     return a;
 }

최소공배수 (LCM)

두 수의 공통된 배수 중 가장 작은 정수
GCD를 이용해 구할 수 있음
A B = GCD LCM

소수

약수가 1과 자기 자신 밖에 없는 수

관련 알고리즘1 : 어떤 수 N이 소수인지 아닌지 판별

2부터 N-1까지 나누어서 확인

//O(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;
}

2부터 N/2까지 나누어서 확인 (약수 중 가장 큰 수는 N/2보다 작거나 같기 때문)

//O(N)
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;
}

2부터 루트N까지 나누어서 확인 (N = a * b 일 때, a <= 루트N, b >= 루트N 이기 때문)

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

관련 알고리즘2 : N이하의 소수를 찾는 방법

1부터 N까지 소수인지 아닌지 하나씩 확인, O(N*루트N)

에라토스테네스의 체 (가장 빠른 방법)

int prime[100]; //소수 저장
int pn = 0; //소수의 개수
bool check[101];    //지워졌으면 true
int n= 100;
for(int i = 2; i <= n; i++) {
    if(check[i] == false){
        prime[pn++] = i;
        for(int j = i*i; j <= n; j += i) {
            check[j] = true;
        }
    }
}
//안쪽의 for문에서 i*i가 i=1,000,000일 경우 int의 표현범위인 21억을 넘기 때문에 문제가 있을 수도 있어 i*2, i+i와 같이 바꾸는 것이 좋음

골드바흐의 추측
- 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다.
- 위 문장에 3을 더하면 5보다 큰 모든 짝수는 세 소수의 합으로 표현 가능하다.
- 10^18 이하에서는 참으로 증명됨
- N = a + b (a, b는 소수)를 구할 때, 에라토스테네스의 체를 사용해 범위 내의 모든 소수(a)를 구한 뒤, N - b가 소수인지 판별하는 방식으로 구할 수 있다. N - b가 소수인지 아닌지는 check배열로 검사하면 된다.

팩토리얼

N! = 1 2 … * N
10! = 3628800

나머지 연산

최대공약수 (GCD)

최소공배수 (LCM)

소수

팩토리얼

관련 연습문제

Ujoy