정수의 임의의 거듭제곱들의 합을 바라보는 놀라운 방법

15319번: 동혁이의 생일선물 정수 x의 거듭제곱 $x^{0}, x^{1}, x^{2}, ...$에 대하여 이들의 모든 부분집합 A1, A2, ...을 생각하자 각 부분집합의 원소들의 합을 M1, M2,...라고 할 때 이들을 오름차순으로 정렬하면 수열 a1, a2,...를 얻는다 이때 k번째 원소 ak에 대하여 n개의 x,k가 주어질때 각각 구한 모든 ak의 합을 10^9 + 7로 나눈 나머지를 구한다 --------------------------------------------------------------------------------------------------------------------------------------------------------------- 2,3,4,....

• format_list_bulleted 정수론
• · 2025. 2. 11.
• textsms

키타마사 법(kitamasa method, きたまさ法)에 대한 공부

1. 키타마사 법(kitamasa method) 수열 $a_{n}$의 점화식을 이전의 몇개 항으로 정의한다면, 귀납적 정의, 재귀적 수열 등으로 부른다. $$a_{n} = \sum_{i = 1}^{k} w_{i}a_{n-i}$$ 이런 형태로 정의되는 대표적인 수열은 피보나치 수열이다. $$a_{n} = a_{n-1} + a_{n-2}, w_{1} = w_{2} = 1, k = 2$$ 이 피보나치 수열의 가장 빠른? 해법중 하나는 행렬을 이용하는 방법이다. https://deepdata.tistory.com/760 행렬을 이용한 피보나치 수열 문제의 해법 1. 피보나치 수열의 행렬 표현 피보나치 수열의 점화식은 다음과 같다. $a_{n+1} = a_{n} + a_{n-1}$ $a_{n} = a_{n} + ..

• format_list_bulleted 대수학
• · 2023. 8. 27.
• 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

최대공약수 파헤치기1 - N*M 최대공약수 테이블이 만들어내는 아름다운 패턴

1. 문제 14860번: GCD 곱 (acmicpc.net) 14860번: GCD 곱 N과 M 이 주어졌을 때, GCD(1, 1) × GCD(1, 2) × ... × GCD(1, M) × GCD(2, 1) × GCD(2, 2) × ... × GCD(2, M) × ... × GCD(N, 1) × GCD(N, 2) × ... × GCD(N, M)을 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 풀이 N*M 테이블에서 최대공약수를 구해본다. 예를 들어 N = 10, M = 10이라고 한다면.. 1은 곱해봤자 의미없으니까 2부터 테이블에 몇개나 나타나는지 한번 찾아보면 5*5 = 25개 있다는 것을 알 수 있는데 이는 행과 열에서 2의 배수가 몇개나 있는지를 세면 된다는 것을 볼 수 있다. 길..

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

피보나치 수열 심화과정2 - 자연수 n이 피보나치 수인지 바로 알 수 있을까? -

1. 주어진 수가 피보나치 수인지 바로 알 수 있을까? 피보나치 수는 $F_{1} = F_{2} = 1$이고 $F_{i} = F_{i-1} + F_{i-2}$을 만족하는 $F_{i}$이다. 반대로 어떤 자연수 n이 주어질때 그 수가 피보나치 수열 $F_{i}$의 하나인지 바로 판단할 수 있을까? 2. 행렬을 이용해 피보나치 수를 만드는 방법 일반적으로는 $F_{1} = F_{2} = 1$부터 차근차근 만들어나가는 것이다. 그러면 언젠가 주어진 자연수 n 근처에 도달할 것이고, n에 정확히 도달하면 n은 피보나치 수이고 n을 넘어가면 n은 피보나치 수가 아니다. 행렬을 이용한 피보나치 수 생성하는 방법이 O(logN)으로 가장 빠르면서 유의미한데, 이정도만 해도 사실 상당히 빠르다 https://deepd..

• format_list_bulleted 정수론
• · 2023. 5. 23.
• textsms