# number theory
LeetCode - 1979. Find Greatest Common Divisor of Array
구하고자 하는 것은 수열에서 최댓값과 최솟값의 최대공약수이다.1\. 수열에서 최댓값과 최솟값을 얻어낸다.2\. 최대공약수는 아무리 커도 최솟값보다 클 수 없다.그렇기 때문에 최솟값에서 1씩 빼면서 최대공약수인지 확인해본다.3\. 최솟값과 최댓값이 둘 다 나누어 떨어질때
LeetCode - 2427. Number of Common Factors
이 문제는 두 수의 공약수를 찾는 문제이다.필자는 while문을 통해서 풀었다.공약수가 아무리 커도 두 수보단 클 수 없으므로 조건식으로 x <= Math.min(a, b)를 작성하였다.그리고 x(확인할 수)를 1부터 1씩 증가시키면서 두 수가 나누어 떨어지는 확
LeetCode - 2652. Sum Multiples
크게 어렵지 않은 문제였던 것 같다. 요구하는대로 단순하게 작성해봤다.3, 5, 7로 나누어 떨어질 경우에만 sum에 더해지도록 작성했다.
LeetCode - 2413. Smallest Even Multiple
생각보다 간단한 문제였다.n이 2로 나누어 떨어지면 n를 리턴하면되고 아니면 2를 곱한 수를 리턴하면된다.
백준 28427
다음 쿼리를 수행하는 프로그램을 작성하시오.$L\\ R$: $L \\leq x < y \\leq R$을 만족하는 정수 $x$, $y$에 대하여, $x \\leq k \\leq y$를 만족하는 모든 자연수 $k$의 합이 소수가 되게 하는 모든 정수 쌍 $(x, \
백준 28426
다음 두 조건을 만족하는 길이 $N$의 수열 $A_1,A_2,\\cdots,A_N$을 아무거나 하나 구해서 출력해 보자.수열의 원소는 모두 다르고 $2$ 이상 $10^6$ 이하의 정수이다.$1$ 이상 $N$ 이하의 모든 정수 $i$에 대해서, $A_i$가 $A_1+A_
[정수론] 백준과 함께 하는 정수론 - 3
[BOJ 2485번 가로수] 임의의 간격으로 배열 되어있는 가로수들이 모두 같은 간격이 되도록 가로수를 새로 심어야 하는 최소수를 구하는 문제이다. 1 3 7 13 위치에 있다면 1 3 5 7 9 11 13 과 같이 3그루를 심어주면 된다. 심는 가로수가 최소가 되
[정수론] 백준과 함께 하는 정수론 - 2
문제는 간단하다. 자연수 $n$이 주어졌을 때, $GCD(n, k)=1$ 을 만족하는 자연수 $1\\leq k\\leq n$ 의 개수를 구하면 되는 문제이다.그냥 단순히 $O(N)$ 으로 반복문을 전부 돌려보며 카운팅을 하면 안되냐 할 수 있겠지만 $n$ 의 제한을 보
[정수론] 백준과 함께 하는 정수론 - 1
$\\binom{n}{k}$ % 1,000,000,007 을 구하는 문제이다. 결론적으로 이 문제는 모듈러의 성질, 페르마의 소정리와 분할 정복을 이용해 해결 가능하다. 본문에 나오는 $p$는 소수 (1,000,000,007) 임을 인지하자.우선 페르마의 소정리는 아래
[Cryptography(암호학)] 5주차-Number Theory
본 포스팅은 Coursera | Cryptography - Jonathan Katz 강의를 수강하며 정리했습니다.Cryptography 4주차 강의정리를 시작하겠습니다. 이번 주차에서는 비대칭키 암호화를 위한 number Theory(정수론)에 대해 공부합니다. 이번
[백준] 검문
M : 같은 나머지를 가지게 하는 수N개의 수들은 다음과 같이 표현가능하다.v0 = q$\_0$ \* M + rv1 = q$\_1$ \* M + rv2 = q$\_2$ \* M + r...vn-2 = q$\_1$ \* M + rvn-1 = q$\_1$ \* M + r위
