수학1

나머지연산

• 정답을 향해 갈때마다 갱신해줘야 할때 나머지연산을 실행한다.
• 나눗셈은 성립하지 않는다.
• 나머지연산 결과는 무조건 -c < ㅁ < c 이다.
• 나머지연산 결과가 음수이면 (ㅁ+c)%c 해주면 된다. 왜냐하면 (0< ㅁ+c < 2c ) % c 연산이기때문이다.

최대공약수

• 유클리트 호제법 gcd(a,b) = gcd(b,r) -> r(==a%b)이 0이 나올때 b가 최대공약수

최소공배수

• A X B = GCD X LCM
• LCM = AXB / GCD

최소공배수 문제

1. 최대공약수와 최소공배수(https://www.acmicpc.net/problem/2609)
2. 최소공배수(https://www.acmicpc.net/problem/1934)

소수

• 2보다 크거나 같고, N-1보다 작거나 같은 자연수로 나누어 떨어지면 안되는 수.

어떤 수 N이 소수인지 아닌지 판별하는 문제

1. N이 소수가 되려면, 2보다 크거나 같고, N/2보다 작거나 같은 자연수로 나누어 떨어지면 안된다. (N != a(2) * b(N/2))
2. N이 소수가 되려면, 2보다 크거나 같고, √n보다 작거나 같은 자연수로 나누어 떨어지면 안된다. (N != a(<=√n) * b(>=√n)) → (조건식에 i<=√n -> i^2 <= n) = 시간복잡도(O(√N))

문제

1. 소수찾기(https://www.acmicpc.net/problem/1978)

N보다 작거나 같은 모든 자연수 중에서 소수를 찾아내는 문제

1. N보다 작거나 같은것에 대해 위 알고리즘 실행 = 시간복잡도(O(N√N)) -> 느린편이다
   2. 에라토스테네스의 체:
   - 지워지지 않는 수 중에서 가장 작은 수는 2이다.
   - 2는 소수이고 2의 배수를 모두 지운다.
   - 위 과정(3->5->7)을 반복한다.
   - 3 X 2 는 이미 2의 배수부분에서 지워져있다
   - a X b 에서 a보다 작은 b가 먼저 지우기때문에 b가 a보다 클때부터 지우면된다.
   - 남아 있는 수는 모두 소수이다.
   

문제

1. 소수찾기(https://www.acmicpc.net/problem/1929)

골드바흐의 추측

• 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다.
• 위 문장에 3을 더하면
• 5보다 큰 모든 홀수는 세 소수의 합으로 표현 가능하다.
• 로 바뀐다.
• 아직 증명되지 않은 문제

문제

1. 골드바흐의 추측(https://www.acmicpc.net/problem/6588)

+α

• 모든 소수는 6n+1 or 6n+5의 형태이다.

팩토리얼

• 매우 큰 값 -> 브루트포스에서 주로 사용됨

문제

1. 팩토리얼(https://www.acmicpc.net/problem/10872)
2. 팩토리얼 0의 개수(https://www.acmicpc.net/problem/1676)
3. 조합0의 개수(https://www.acmicpc.net/problem/2004)

연습문제

1. gcd합(https://www.acmicpc.net/problem/9613)
2. 숨바꼭질6(https://www.acmicpc.net/problem/17087)
3. 2진수8진수(https://www.acmicpc.net/problem/1373)
4. -2진수(https://www.acmicpc.net/problem/2089)
5. 골드바흐 파티션(https://www.acmicpc.net/problem/17103)