(작성중)정수론

입문

---

0. 알아둬야 할 부분

이 내용은 정수론 교과서를 따라간 것이 아니라, 알고리즘 문제를 풀면서 나에게 필요한 부분만 공부한 것이고, 주관적인 부분이 많이 섞여 있으며, 틀린 부분이 있을 수 있으니 그냥 참고만 하자

정수론 문제들은 대부분 엄청나게 큰 수까지의 범위를 다룬다. 오버플로우에 조심하자. 아니면 다른 특별한 아이디어가 필요한 문제일지도 모른다. 그냥 파이썬 쓰면 쉽게 풀릴지도 모른다...

그리고 정수론 문제 풀다가 잘 모르겠으면 그냥 풀이를 보자. 정수론은 정말 알면 쉽게 풀지만 모르면 못 푼다고 생각한다.

---

1. sqrt, ceil, floor, round

이녀석들은 SQL을 하든 엑셀을 하든 어떤 언어를 공부하든 가장 기본적이고 유용하게 쓰일 녀석들임

C++에서 정수끼리의 나눗셈 결과는 실수로 나온 결과에 floor을 했다고 생각하면 된다(실수부를 0으로 만든다)

https://en.wikipedia.org/wiki/Floor_and_ceiling_functions

Floor and ceiling functions - Wikipedia

 

floor(sqrt(M))^2 <= M <= ceil(sqrt(M))^2 가 성립한다.

M이 제곱수일 경우, 

floor(sqrt(M))^2 = M = ceil(sqrt(M))^2 이 성립한다.

 

관련 문제:

https://atcoder.jp/contests/abc296/tasks/abc296_d

D - M<=ab

 

** Truncate라는 녀석도 존재한다. '자르다'의 의미를 갖는다. 보통 몇번째 글자까지만 표시하기 위해 사용함.

 

2. 배수와 약수

배수는 컴퓨터로 쉽게 계산할 수 있으나, 1,2,3,4,5,6,7,8,9 의 배수 판정법을 알아야 풀 수 있는 문제가 드물게 있다

1의 배수	모든 수는 1의 배수임
2의 배수	마지막 숫자가 2로 나누어떨어짐
3의 배수	모든 자리 숫자의 합이 3의 배수임
4의 배수	마지막 두 자리가 00이거나 4의 배수임
5의 배수	마지막 숫자가 5 아니면 0임
6의 배수	모든 자리 숫자 합이 3의 배수이면서, 짝수
7의 배수	까다로우니 직접 검색해 보자
8의 배수	마지막 세 자리가 000이거나 8의 배수
9의 배수	모든 자리 숫자의 합이 9의 배수임

 

배수의 계산은 쉬운데 약수는 컴퓨터로 쉽게 계산할 수 없다. 1부터 sqrt(n) 까지의 숫자를 일일히 확인하면서 나머지 연산이 0이 되는지 확인해야 한다.

관련 문제 :
2022년이 아름다웠던 이유(브론즈 1) : 생각보다 귀찮다 https://www.acmicpc.net/problem/27065

 

 

---

3. 모듈러 연산의 성질, 합동식

알다시피 C++ 에서 나머지 연산은 %로 한다.
3%2 = 1이고,
-1%2 = -1이다.

정수가 아닌 수에 대해서 나머지연산을 하려고 하면 오류가 난다

합동식 표현을 익혀두면 편하다. 왜냐면 앞으로 정수론 공부할때마다 나올거거든!!!
3%2 = 1 을 합동식으로 표현하면, 3 ≡ 1(mod 2) 로 표현할 수 있다.

 

합동식의 중요한 성질은 덧셈, 뺄셈, 곱셈에 대해 교환법칙과 분배법칙이 성립한다는 것이다. 일단 이정도만 알아두면 된다.

어떤 문제의 결과값이 매우 크게 나올 때 모듈러 연산의 성질이 자주 사용된다.
매우 큰 수를 나누기 위해 주로 사용되는 숫자는 1e9+7이다. 1e9+7은 int의 max값에 가까우면서, 소수이다.

나무위키 - 합동식 : https://namu.wiki/w/%ED%95%A9%EB%8F%99%EC%8B%9D

 

관련 문제 :
곱셈(실버1) : 거듭게곱의 모듈러 연산이 어떻게 될지 생각해 보자. https://www.acmicpc.net/problem/1629

위 문제를 풀려면 분할 정복을 통해 시간복잡도를 크게 줄여야 한다.

 

 

 

---

4. 조합, 파스칼의 삼각형

물건 n개가 있을 때 순서를 신경쓰지 않으면서 k개를 고르는 경우의 수이다.

 

nCk = n!/(n-k)!/k! = n(n-1)(n-2)...(n-k+1) / (k(k-1)(k-2)...(1))

팩토리얼 형태는 재귀적으로 (또는 반복문으로) 계산할 수 있으나, 파스칼의 삼각형을 이용하면 dp를 이용한 풀이가 가능하다.

중요 성질 1) nCk = n-1Ck + n-1Ck-1 이다.

중요 성질 2) nC0+nC1+...+nCn = 2^n 이다.

조합은 이항 계수라는 이름으로도 등장하고, 많은 성질들이 존재하고, 수학적으로 중요하지만 일단 이 정도만 알아두면 된?다

 

---

5. 최대공약수 gcd

이것도 너무 중요하다 이건 그냥 구현하는 함수를 외워 놓자

유클리드 호제법이라는 방법을 사용해, 최대공약수를 구한다. 그냥 함수를 통으로 외우자 뼈가되고 살이되고

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
using namespace std;

ll get_gcd(ll a,ll b){
	if(b>a){
    	ll c = a;
        a = b;
        b = c;
    }
    ll r = a % b;
    while(r){
    	a = b;
        b = r;
        r = a % b;
    }
    return b;
}

int main(void) {
    fastio;
    cout<<get_gcd(24,60);
    return 0;
}

실행결과 >> 12

 

관련 문제:

외로운 곰곰이는 친구가 있어요(골드3) : 아는사람은 케이크처럼쉽게먹었다는 쉬운문제  https://www.acmicpc.net/problem/26073

검문(골드4) : 힘들게 풀었다 https://www.acmicpc.net/problem/2981

 

---

6. 소수 찾기, 소수의 성질

에라토스테네스의 채를 이용한다. 그리고 n까지의 소수를 찾으려면 sqrt(n) 까지만 확인하면 된다.

뭐라고 할까??

그냥 문제를 풀어 보자

 

관련 문제 : 

소수 구하기(실버3) : 소수 찾는 방법은 알고 있어야 한다 https://www.acmicpc.net/problem/1929

---

 

괜찮은데 어디 들어갈지 모르겠는 문제들:

청기 백기(실버4) : 잘 생각하면 쉬운 풀이가 나온다 

예쁜 케이크(실버2) : 쉽고빨리풀리고간단하고쉽고짧고좋은문제 https://www.acmicpc.net/problem/24040

직육면체(골드5) : 쉽고빨리풀리고간단하고짧은문제 https://www.acmicpc.net/problem/27087

 

---

심화

---

1. 페르마의 소정리

위에서 배운 모듈러 연산과 합동식 개념을, 나눗셈까지 확장한다. "모듈러 역원" 에 관한 내용을 배운다.

https://www.acmicpc.net/problem/11401

정말 모르겠어서 풀이를 보고 푼 문제이다.

 

B^(P-2) ≡ B^-1 (mod P) 이다. 모듈러 연산을 분수(나눗셈) 까지 확장할 수 있다.

---

2. 오일러의 정리

 

3. 중국인의 나머지 정리

 

 

나무위키 - 중국인의 나머지 정리 : https://namu.wiki/w/%EC%A4%91%EA%B5%AD%EC%9D%B8%EC%9D%98%20%EB%82%98%EB%A8%B8%EC%A7%80%20%EC%A0%95%EB%A6%AC

카잉 달력(실버 1) : 이게 중국인의 나머지 정리 문제인 지 모르고 그냥 풀었다. 시간복잡도 내에 푸는 것은 쉬우나 실수하기 어려운 문제라고 느꼈다. https://www.acmicpc.net/problem/6064

 

4. 윌슨의 정리

 

5. 빠른 소인수분해

 

뤼카의 정리

확장 유클리드 알고리즘

밀러-라빈 소수판정법

폴라드 로 알고리즘(빠른 소인수분해)

FFT?