정수론(Number theory)
-
백준 1065번: 한수정수론(Number theory) 2018. 7. 3. 09:57
https://www.acmicpc.net/problem/1065 1. 문제어떤 양의 정수 X의 자리수가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. 2. 알고리즘키워드 - 수학, 구현 문제를 접근 하기 위해서는 먼저 등차 수열이 무엇인지를 이해 해야 한다. 수학에서, 등차수열(等差數列, 문화어: 같은차수렬, 영어: arithmetic sequence)은 연속하는 두 항의 차이가 모두 일정한 수열을 뜻한다. 예를 들어 1, 3, 5, 7, 9, ...은 등차수열이다. 이때 두 항의 차이는 이 수열의 모든 연속하는 두 항들에 대해서 공통..
-
백준 13241번: 최소공배수정수론(Number theory) 2018. 7. 3. 09:49
https://www.acmicpc.net/problem/13241 1. 문제두 수의 최소 공배수를 찾는 문제 2. 알고리즘키워드 - 유클리드 호제법, GCD 3. 코드 123456789101112131415161718192021#include #include #include #include #include // greater 사용 위해 필요 #include #include #include using namespace std;long long int gcd(long long int a,long long int b) { return (a % b == 0 ? b : gcd(b,a%b));}int main() { long long int a, b; cin >> a >> b; long long int sol =..
-
백준 1019번: 책 페이지정수론(Number theory) 2018. 7. 1. 19:05
https://www.acmicpc.net/problem/1019 1. 문제지민이는 N쪽인 책이 한권 있다. 첫 페이지는 1쪽이고, 마지막 페이지는 N쪽이다. 각 숫자가 모두 몇 번이 나오는지 출력하는 프로그램을 작성하시오. 2. 알고리즘키워드 - 정수론참고 - https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1019 3. 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include #include #include #include #include ..
-
백준 4673번: 셀프 넘버정수론(Number theory) 2018. 6. 29. 17:00
https://www.acmicpc.net/problem/4673 1. 문제셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다. 33, 39, 51, 57, 69, 84, 96, 111, 114..
-
백준 10610번: 30정수론(Number theory) 2018. 6. 29. 13:41
https://www.acmicpc.net/problem/10610 1. 문제어느날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. (그 수가 존재한다면) 2. 알고리즘키워드 - 정수론, 그리드 알고리즘 30 이란 숫자를 분리 하면 [3, 0] 으로 분리 할 수 있다.분리된 수의 합은 3 임으로 3의 배수이다.숫자 [3, 0] 의 조합으로 만들 수 있는 30의 배수 중 가장 큰 수는 [30] 이다. 숫자 102를 분리 하면 [1, 0, 2] 으로 분리 된다.분리 된 수의 합은 3 임으로 3의 배..
-
백준 5086번: 배수와 약수정수론(Number theory) 2018. 6. 21. 17:10
https://www.acmicpc.net/problem/5086 1. 문제4 × 3 = 12이다.이 식을 통해 다음과 같은 사실을 알 수 있다.3은 12의 약수이고, 12는 3의 배수이다.4도 12의 약수이고, 12는 4의 배수이다.두 수가 주어졌을 때, 다음 3가지 중 어떤 관계인지 구하는 프로그램을 작성하시오.첫번째 숫자가 두번째 숫자의 약수이다.첫번째 숫자가 두번째 숫자의 배수이다.첫번째 숫자가 두번째 숫자의 약수와 배수 모두 아니다. 2. 알고리즘배수 판별식 - K % N == 0 / N % K == N약수 반별식 - N % K == 0 / K % N == K 3. 코드12345678910111213141516171819202122232425262728293031323334353637383940..
-
백준 2581번 : 소수정수론(Number theory) 2018. 6. 20. 12:16
https://www.acmicpc.net/problem/2581 1. 문제자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최소값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최소값은 61이 된다. 2. 알고리즘소수의 합을 저장 할 SUM 이라는 변수를 선언한다.소수 판별을 하여 소수이면 SUM 에 적산 한다. 소수 중 가장 작은 값을 찾기 위해 CAND 라는 변수를 선언 하고 987654321 로 초기화 한다.소수 판별을 하여 소수이면 CAND 보다 작다면 CAND 를 현재 값으로 치환..
-
백준 1978번 : 소수 찾기정수론(Number theory) 2018. 6. 20. 12:07
https://www.acmicpc.net/problem/1978 1. 문제주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 2. 알고리즘소수인지 판별 하여 소수인 수를 카운트를 하여 출력 3. 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #include #include #include #include #include #include #include #include #include using namespace std; /** @brief - 소수 판별*/int prime(int n){ if (n == 1) { re..