[TIL] 알고리즘 : 정수론

Chap 3 . 정수론

summary
- 유클리드 호제법 : 빠르게 최대공약수 구할 수 있음
- 확장 유클리드 호제법 : 특정 방정식의 해 구할 수 있음 ( ax + by = 1 꼴 )
- 에라토스테네스의 체 : 소수 판별
- 서로소, 인수분해, 최소공배수, 최대공약수 -> '소수'를 활용하자

슬슬 체력 한계가 느껴진다 오늘은 꼭 일찍자야겠다 모르는 문제 너무 오래 끌지말고 넘어가자.. !!

1 ) 항등식 & 합동식

- 합동식 : a를 p로 나눈 나머지 = b를 p로 나눈 나머지 (글쿤)

 

2 ) 유클리드 호제법

: 최대공약수 구하는 가장 빠른, 효율적인 방법

- 원리: a%b=r 일때, a와 b의 쵣대 공약수 = b와 r의 최대공약수

 

- 구현

1. 재귀
2. 반복문 (추천)

- 활용

• 기약분수 : 최대공약수로 나눈 상태의 분수
• n개의 수에 대한 최대공약수

- 코드

int gcd(int a, int b){ //b<a 
	int c;
	while(b){
		c= a % b;
		a=b;
		b=c;
	}
	return a; //최대공약수 반환
}

 

3 ) 방정식

• 디오판토스 방정식 : 해가 정수인 경우의 부정방정식 ax + by = c
• 베주 항등식 : ax + by = gcd( x,y ) 만약 x,y가 서로소라면 gcd(x,y)=1므로 유용함

 

4) 확장 유클리드 호제법

: 점화식으로 ax+by=1의 해를 빠르게 구하는 방법. C++에서는 동적 할당을 위해 vector 사용하자. 행렬처럼 생각하쇼

 

- 대략 과정

1. 나머지 끼리 연산
2. 해 구하기

- 코드

============================== 
                 나머지  몫 
       s    t      r    q 
      { 1 , 0 }  { a }  
      { 0 , 1 }  { b } 
=============================== 

// 확장유클리드 호제법 
// ax + by = gcd(a,b) 가 되는 x, y 를 구함 

pii extendedGcd(int a, int b) { 
 vector<int> s = { 1,0 }; 
 vector<int> t = { 0,1 }; 
 vector<int> r = { a, b }; 
 vector<int> q; 

 while (1) { 
      // 1단계 - 나머지끼리 연산 
  int r2 = r[r.size() - 2]; 
  int r1 = r[r.size() - 1]; 
  q.push_back(r2 / r1); 
  r.push_back(r2 % r1); 

      // ** 탈출조건  
  if (r[r.size() - 1] == 0) { 
   break; 
  } 

 // 2단계 - s, t 구하는 점화식 
  int s2 = s[s.size() - 2]; 
  int s1 = s[s.size() - 1]; 

  int t2 = t[t.size() - 2]; 
  int t1 = t[t.size() - 1]; 

  int q1 = q[q.size() - 1]; 
  s.push_back(s2 - s1 * q1); 
  t.push_back(t2 - t1 * q1); 
 } 

 // { x, y } 
 pii ret = { s[s.size() - 1], t[t.size() - 1] }; 

 return ret; 
}

 

4 ) 소수

 

- N이 주어졌을때, 소수인지 판단하기 (숫자 한개 주어졌을때)

1.  2 ~ N 까지의 수로 나눠보기 (x, 시간복잡도 O(N)) 
2.  2 ~ 루트 N 까지의 수로 나눠보기 (x, 시간복잡도 O(루트N))
3. 루트 N 보다 작은 '소수'로 나눠보기 (시간복잡도 O(루트N * ln루트N))

 

- 에라토스테네스의 체

: 백만 이하의 모든 소수를 찾을 수 있는 유용한 방법. 소수를 찾고, 그 소수의 배수를 모두 지워 나가기

 

- 활용

• 소수 배열에서 연속된 소수의 합 구하기 -> 2 pointer
• 소인수 분해
• 서로소

 

끝~ 오늘은 정리할 내용자체는 안많네 

몸이 으슬으슬한것이 컨디션이 영 안좋다 ㅜ

오늘은 꼭 12시 전에 도착하쟈

백준 풀어보쟝~~~