수학 - 나머지 연산, GCD, LCM, 진법, 소수

● 나머지 연산

> (A + B) mod M = ((A mod M) + (B mod M)) mod M

> (A * B) mod M = ((A mod M) * (B mod M)) mod M

> 나누기의 경우는 성립되지 않음.

> (A - B) mod M = ((A mod M) - (B mod M) + M) mod M

     - 뺄셈의 경우에는 마이너스가 나올 수 있기 때문에 M을 더해주어야 한다.

 

 

● GCD(최대공약수) - 유클리드 호제법

> 최대공약수를 구하는 가장 쉬운 방법은 2부터 min(A, B)까지 모든 정수로 나눠보는 것이다.

> 하지만, 속도를 높이기 위해 유클리드 호제법을 사용한다.

    - a%b가 r이라고 할때, GCD(a, b) = GCD(b, r)이다.

    - r이 0이면, 그 때의 b가 최대공약수가 된다.

// 재귀함수를 사용하지 않는 유클리드 호제법

int gcd(int x, int y){
    while(y != 0){
    	int r = x % y;
        x = y;
        y = r;
    }
    return x;
}



// 재귀함수를 사용한 유클리드 호제법

int gcd(int x, int y){
    if(y == 0) return x;
    else return gcd(y, x % y);
}

    - 세 수의 최대공약수는 GCD(a, b, c) = GCD(GCD(a, b), c)로 구하면 된다. N개의 최대공약수를 구할때 이를 반복해서 구한다.

 

● LCM - 최소공배수

> GCD를 응용하면 된다.

> A, B 두 숫자와 두 숫자의 GCD가 R일때, LCM = R * (A / R) * (B / R) 이다. 

 

 

● 진법 변환

> 10진법 숫자 N을 B진법으로 바꾸면 그냥 N이 0이 될 때까지 나누기만 하면 된다.

> B진법 숫자 N을 10진법으로 바꾸려면 숫자 한자리마다 B^k를 곱하며 더하면 된다.

> A진법을 B진법으로 바꾸려면, A진법 -> 10진법 -> B진법으로 바꾸면 된다.

// B진법을 10진법으로 바꾸는 코드

#include <iostream>
#include <string>
using namespace std;
int main() {
    int ans = 0;
    string s;
    int b;
    cin >> s >> b;
    for (int i=0; i<s.size(); i++) {
        if ('0' <= s[i] && s[i] <= '9') {
            ans = ans * b + (s[i] - '0');
        } else {
            ans = ans * b + (s[i] - 'A' + 10);
        }
    }
    cout << ans << '\n';
}

 

● 소수

> 소수는 1과 자신만 약수로 가진다.

> N이 소수가 되려면, 2보다 크고, 루트N보다 작거나 같은 자연수로 나눠 떨어지면 안된다. 

    - N이 소수가 아니라면 N = a * b로 나타낼 수 있는데, a * b의 차이가 가장 작은 경우가 루트N이다.

      그렇기 때문에 루트N까지만 검사하면된다.

// 소수 구하는 가장 쉬운 구현
// 시간 복잡도는 O(루트N)

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

 

> 하지만 N의 범위가 커지면, 시간이 너무 오래걸리게 된다. 이 경우, 에라토스테네스의 체를 사용한다.

에라토스테네스의 체는 배열에서 i의 배수를 모두 지워나간다.

// 에라토스테네스의 체 구현

const int MAX = 1000000;
bool check[MAX + 1]; // true: 소수가 아님, false: 소수
void Eratosthenes(){
    check[0] = check[1] = true;
    for(int i = 2; i*i <= MAX; i++) {
        if(check[i] == false) {
            for(int j = i + i; j <= MAX; j += i) {
                check[j] = true;
            }
        }
    }
}

 

- 골드바흐의 추측

> 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다.

> 5보다 큰 모든 홀수는 세 소수의 합으로 나타낼 수 있다.

> 아직 증명되지는 않았지만, 10^18까지는 유효하다.

> 에라토스테네스의 채를 이용하여 구현하면 된다.

 

● 소인수분해

> 정수 N을 소수의 곱으로 분해하는 것. 소수를 구하지 않고도 구현 가능하다.

> N을 소인수분해 했을 때, 나타날 수 있는 인수 중 가장 큰 값은 루트N이다.(즉, i*i <= N까지만 돌면 된다.)

// 소인수분해 구현

for(int i = 2; i*i <= n; i++){
	while(n % i == 0){
    	cout << i;
        n /= i;
    }
}

// i는 n의 인수.