1. 오일러의 정리(Euler's theorem) a와 n이 서로소인 양의 정수이면, 다음이 성립한다 $$a^{\varphi(n)} \equiv 1 (mod n)$$ 여기서 $\varphi(n)$은 n에 대한 오일러 phi 함수이다. 서로소가 아니라면 다음과 같이 쓸 수 있다. $$a^{\varphi(n) + 1} \equiv a (mod n)$$ n이 소수 p이면, $\varphi(p) = p-1$이므로, a,p가 서로소이면 $a^{p-1} \equiv 1 (mod p)$이다. 페르마의 소정리는 오일러의 정리의 특수한 케이스이다. 2. 거듭제곱을 어떤 정수로 나눈 나머지 $a^{n}$을 어떤 정수 p로 나눈 나머지는 어떻게 구할 수 있을까? $a^{n}$을 직접 계산한 다음에, p로 나눈 나머지를 구하..
1. 페르마의 소정리(Fermat's little Theorem) 1-1) p가 소수이고, a가 p의 배수가 아니면( = a와 p가 서로소이면 = gcd(a,p) = 1)이면, $$a^{p-1} \equiv 1 (mod p)$$이다. 1-2) p가 소수이면, 모든 정수 a에 대하여 $$a^{p} \equiv a (mod p)$$ 응용하는 방법은 여러가지가 있겠지만, 하나하나 다 나열할 수도 없고, 접한지 얼마 안되었으니 나도 다 모르고 증명도 굳이 할 필요없을 것 같고, 받아들이면서 문제를 풀면서 익혀보기로 하자 2. 응용 - 합성수 판정 페르마의 소정리 역은 성립하지 않는다. 즉, a와 p가 서로소일때, $$a^{p-1} \equiv 1 (mod p)$$가 성립한다면, p는 소수이다는 거짓이다. 즉, ..
1. 오일러의 phi 함수(Euler's phi function, totient function) $\varphi(n)$은 1부터 n까지의 자연수 중에서 n과 서로소인 자연수의 개수로 정의한다. 그 성질과 응용이 매우 다양하고 또 매우 어려운데... 하나하나 파고들면 끝도 없으니까 문제 풀면서 익히기로 하자 2. 구현 예시1 - 가장 간단한 구현 가장 간단한 방법은 1이상 n이하의 자연수 중에서, n과 서로소인 것의 개수를 세보면 된다. 그러니까 1이상 n이하의 자연수 중에서 n과 최대공약수가 1인 자연수의 개수가 n이하에서 몇개인지 세보면 된다. 유클리드 호제법을 이용해서 최대공약수를 구하는 함수를 만들고, def gcd(a,b): while b != 0: a,b = b,a%b return a 2부터 ..
1. 문제 5676번: 음주 코딩 (acmicpc.net) 5676번: 음주 코딩 각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다. www.acmicpc.net 특정 구간의 수열의 곱이 양수인지 음수인지 0인지 판단하거나 특정 인덱스의 원소를 바꾸는 쿼리를 수행하는 문제 2. 곱셈의 시간복잡도 매우 큰 수를 곱할수록 프로그램의 시간복잡도가 높아진다. 이게 몇번만 연산하면 별로 차이 없어보이지만 10만번이나 반복연산해야한다면, 눈에띄게 느려진다 매우 큰 4개의 수를 곱하는 과정을 10만번 반복했는데 평균적으로 0.03초 걸린다면... 단순히 1,2,3,4 4개..
1. 문제 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 00과 1을 이용해서 만들 수 있는 길이 n의 이진수열의 개수를 15746으로 나눈 나머지를 구하는 문제 2. 풀이 가능한 경우의 수를 나열해서 규칙을 찾으면 간단해진다 1,2,3,5,8,...로 이어져서 피보나치 수열이라는 느낌이 온다 그래서 한번 해보면 from sys import stdin n = int(stdin.readline()) dp = [0] * 1000001 dp[1] = 1..
1. 문제 https://www.acmicpc.net/problem/10158 10158번: 개미 가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오 www.acmicpc.net 좌표평면 안에서 개미가 대각선 방향으로 움직이는데, 벽면에 부딪힐 경우, 반사되어 움직인다. 일정한 속력으로 움직일 때, 평면의 크기, 처음 좌표가 주어지고 시간 t가 주어질때, t시간 후에 개미의 위치를 구해본다면..? 2. 풀이 시간 t의 범위가 2억이나 되니까, 일반적인 1칸씩 가는 반복연산으로는 도저히 0.15초만에는 불가능 그렇다고 벽면까지 한번에 가는 방법으..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
