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. 문제1 7516번: 알렉산드리아의 디오판토스 (acmicpc.net) 7516번: 알렉산드리아의 디오판토스 알렉산드리아의 디오판토스는 알렉산드리아에 살던 이집트 수학자이다. 그는 정수로된 해 만을 가지는 다항 방정을 처음으로 연구한 수학자이다. 그를 기리기 위해서 후대에 이 방정식은 디오 www.acmicpc.net 2. 풀이 주어진 방정식 $\frac{1}{x} + \frac{1}{y} = \frac{1}{n}$을 정리하면, $$\frac{y+x}{xy} = \frac{1}{n}$$ 이다. 그래서 $$n(y+x) = xy$$ 를 얻는다. 솔직히 여기서 넘어가기 어려운데, (억지라는 생각이 들 정도..) $n^{2} = pq$라 하자. p,q는 정수이다. 즉, p,q는 $n^{2}$의 약수이다. 그리고..

• format_list_bulleted 정수론
• · 2023. 7. 14.
• 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

n차 다항식 함숫값 빠르게 계산하기(페르마의 소정리로 거듭제곱 빠르게 계산하기)

1. 문제 25025번: 다항식 계산 (acmicpc.net) 25025번: 다항식 계산 첫 번째 줄에 두 정수 $N$, $P$ ($0 ≤ N ≤ 10^6$, $1 ≤ P ≤ 10^3$, $P$는 소수)가 공백 하나로 구분되어 주어진다. 두 번째 줄에는 $N+1$개의 정수 $a_N$, $\cdots$, $a_1$, $a_0$ ($0 ≤ a_i ≤ 10^9$)가 공백 하나로 www.acmicpc.net 2. 풀이 결국에 구해야하는 값은 $a_{i}k^{i} mod P$이고 k와 P가 서로소이므로 페르마의 소정리를 이용할 수 있다. 그런데 1초안에 P개의 값을 계산해야하니 이거 쉽지 않다 계수는 최악의 경우 $10^{6}$개이고.. 매 함숫값마다 이들을 모두 순회해야하니.. $O(10^{9})$는 돌아야겠는..

• format_list_bulleted 정수론
• · 2023. 7. 8.
• 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

이항계수를 소수로 나눈 나머지 구하는 방법 - Lucas' Theorem 배우고 적용하기

https://en.wikipedia.org/wiki/Lucas%27s_theorem Lucas's theorem - Wikipedia From Wikipedia, the free encyclopedia In number theory, Lucas's theorem expresses the remainder of division of the binomial coefficient ( m n ) {\displaystyle {\tbinom {m}{n}}} by a prime number p in terms of the base p expansions of the integers m and n. en.wikipedia.org 1. Lucas' Theorem 정수 m,n과 소수 p에 대하여 $$\binom{m}{n..

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