10진법 정수를 등비수열 합으로 바라보기(Fermat number?)

1. 문제 22445번: Fast Division (acmicpc.net) 22445번: Fast Division イクタ君は速いプログラムが大好きである。最近は、除算のプログラムを高速にしようとしている。しかしなかなか速くならないので、「常識的に考えて典型的」な入力に対してのみ高速に www.acmicpc.net 일본어로 되어있는데 번역하면 $2^{2^{2^{2..}}}$로 총 2가 n개 있을때, 이 값보다 크거나 같은 최소의 소수를 p(n)이라고 정의하자. 여기서 p(0) = 2라고 한다. p(n)-1자리의 10진법 정수 1111....을 p(n)으로 나눈 나머지를 구한다면? 2. 풀이 p(n)을 한번 구해보면.. p(0) = 2 p(1) = 2보다 큰 최소의 소수 3 p(2) = 4보다 큰 최소의 소수 5 p(3) =..

• format_list_bulleted 정수론
• · 2023. 7. 15.
• textsms

포함 배제의 원리를 이용해 매우 큰 범위에서 조건에 맞는 수들만 빠르게 찾는 법 배우기 (+ 부분집합 구하기 재활)

1. 문제 9359번: 서로소 (acmicpc.net) 9359번: 서로소 첫째 줄에 테스트 케이스의 개수 T (0 < T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, A, B, N이 주어진다. (1 ≤ A ≤ B ≤ 1015, 1 ≤ N ≤ 109) www.acmicpc.net 2. 풀이 $10^{15}$이내에서 $N = 10^{9}$과 서로소인 수를 1초안에 찾으라고 한다면.. 보통의 방법으로는 찾기 힘들다 심지어 쿼리로 주어지니 더 어렵다 먼저 약수를 찾는 것보다 배수를 찾는 것이 쉽다는 것을 이해한다. N의 소인수를 모두 찾고, N의 소인수의 배수는 N과 서로소가 아니므로, 이 방법을 이용해 서로소가 아닌 수들을 찾는다. 범위 내에서 N과 서로소인 수와 서로소가 아닌 수로..

• format_list_bulleted 정수론
• · 2023. 7. 9.
• textsms

오일러 phi 함수 재활 -xφ(x) = n을 만족하는 x의 최솟값 구하기-

1. 문제 19577번: 수학은 재밌어 (acmicpc.net) 19577번: 수학은 재밌어 xφ(x) = n을 만족하는 양의 정수 x가 존재하면 최소의 x를, 존재하지 않으면 −1을 출력한다. www.acmicpc.net 2. 풀이 오일러 phi함수를 구하는 방법 n을 소인수분해해서 소인수를 이용해 구하는 방법이 $O(\sqrt{n})$으로 빠르다 https://deepdata.tistory.com/571 오일러의 phi 함수 직접 구현해보면서 개념 익히기 1. 오일러의 phi 함수(Euler's phi function, totient function) $\varphi(n)$은 1부터 n까지의 자연수 중에서 n과 서로소인 자연수의 개수로 정의한다. 그 성질과 응용이 매우 다양하고 또 매우 어려운데.....

• format_list_bulleted 정수론
• · 2023. 7. 6.
• textsms

어떤 수를 서로소 쌍의 곱으로 빠르게 분해하는 방법

1. 문제 2436번: 공약수 (acmicpc.net) 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net 2. 풀이 최대공약수 G, 최소공배수 L이 주어질때 두 수 x,y는 어떻게 구할까 $$x = Gk_{1}$$ $$y = Gk_{2}$$ 이 때 L은 다음과 같이 구할 수 있다 $$L = Gk_{1}k_{2}$$ 따라서 $k_{1}k_{2}$는 L//G로 일정하다. 그러므로 우리는 L//G를 만드는 두 서로소 $k_{1}$과 $k_{2}$를 찾으면 된다. 여기서 $k_{1}$과 $k_{2}$는 1 이상의 자연..

• format_list_bulleted 정수론
• · 2023. 3. 8.
• textsms

중국인의 나머지 정리(Chinese Remainder Theorem) 기본 이해하기

1. 중국인의 나머지 정리(Chinese Remainder Theorem) 정수 $m_{1}, m_{2}, ..., m_{n}$이 임의의 i,j = 1,2,...,n에 대하여 $i \neq j$일때, $m_{i}$와 $m_{j}$가 서로소라면, 즉 $$gcd(m_{i}, m_{j}) = 1, i \neq j$$ 라고 하자. 일차연립합동식 $$x \equiv a_{1} (mod m_{1})$$ , $$x \equiv a_{2} (mod m_{2})$$ , $$x \equiv a_{3} (mod m_{3})$$ , $$\vdots$$ , $$x \equiv a_{n} (mod m_{n})$$ 의 해는 mod $m_{1}, m_{2}, ..., m_{n}$에 대하여 유일하게 존재한다. 2. 보조정리 1 정수 a,b,k..

• format_list_bulleted 정수론
• · 2022. 12. 30.
• textsms

약수를 빠르게 구하는 알고리즘

1. 설명 어떤 자연수 n에 대하여 n = a*b가 되는 두 자연수 a,b를 n의 약수라고 한다. 이러한 a,b는 반드시 존재한다. 최소 (1,n)이 존재한다는 것. n의 약수를 프로그래밍으로 어떻게 구할까? 가장 쉽게 생각하는 방법은 n을 1부터 n까지 각각 나눠보면서 나누어 떨어지는 수를 찾는 것이다. 그런데 n이 너무 크면, 10억만 되어도 너무 오래걸린다는게 문제 ----------------------------------------------------------------------------------------------------------------------- 그런데 n = a*b에서 a,b의 관계를 생각해보면 a > b, a < b, a = b 3가지 경우가 가능하다. 근데 사실 ..

• format_list_bulleted 알고리즘 일반
• · 2022. 8. 10.
• textsms