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

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

-1 의 50만 거듭제곱을 -1**(500000)으로 하면 안되는 이유

파이썬에서 어떤 정수의 거듭제곱을 구한다면 **을 사용한다 print(3**2) 9 그런데 사실 -1의 거듭제곱은 홀수번 거듭제곱하면 -1이고 짝수번 거듭제곱하면 1이다. 그래서 단순히 n이 짝수인지 홀수인지에 따라 (-1)**(n)을 바로 계산할 수 있다 그래봤자 큰 차이 없는거 그냥 하면 되는거 아니냐? 라고 생각할 수 있는데, 한두번 계산하는건 크게 차이 없지만 n이 충분히 클때 (-1)**(n)을 여러번 계산하면 시간차이가 3~4배 정도로 차이가 난다

• format_list_bulleted Python
• · 2024. 2. 17.
• textsms

팩토리얼을 계산하지 않고도 소인수분해하는 기본기

1. 문제 15996번: 팩토리얼 나누기 (acmicpc.net) 15996번: 팩토리얼 나누기 음이 아닌 정수 N와 소수(prime number) A가 주어지면, N!을 Ak로 나누었을 때, 나머지가 0이 되는 최대의 음이 아닌 정수 k를 구하여라. (단, N!=N×(N-1)×···×1, 0!=1) www.acmicpc.net 2. 풀이 n의 범위가 $2^{31} = 2147483648$까지로 이것의 팩토리얼을 계산하면... 상상하기도 힘든 숫자가 나올거는 뻔하니 계산하지 않고 $A^{k}$로 나눠보라는 말일텐데 어떻게 가능할까 예를 들어 생각하면 생각보다 간단한 문제다 5! = 5*4*3*2*1인데 $2^{k}$로 나눈 나머지가 0이 되는 최대의 k는 어떻게 찾을까 만약 k = 0이면 당연히 5!은 ..

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

비트마스크를 이용한 에라토스테네스의 체 배우기

1. 에라토스테네스의 체 기본형태 n이하의 소수를 구하는 알고리즘 n+1개의 1을 가지는 리스트로 초기화하고, 2부터 n의 제곱근까지 순회하여 해당 수의 배수를 모두 지우고 나면 소수만 남는다는 알고리즘이다 n = int(input()) result = [1]*(n+1) for i in range(2,int((n+1)**(1/2))+1): if result[i] == 1: for j in range(i*i,n+1,i): result[j] = 0 prime_list = [i for i in range(2,n+1) if result[i] == 1] 여기서 j의 시작 지점을 i+i로 하는 경우가 많은데, i*i로 해도 된다. 왜냐하면, i+i는 결국 가장 먼저 2의 배수에서 지워지기 때문이다. 2. 에라토스테..

• format_list_bulleted 비트마스킹
• · 2023. 5. 4.
• textsms

행렬을 이용한 피보나치 수열 문제의 해법

1. 피보나치 수열의 행렬 표현 피보나치 수열의 점화식은 다음과 같다. $a_{n+1} = a_{n} + a_{n-1}$ $a_{n} = a_{n} + 0$ 따라서 행렬로 나타내면 다음과 같다 $$\begin{pmatrix} a_{n+1} \\ a_{n} \end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 1 & 0 \\ \end{pmatrix}\begin{pmatrix} a_{n} \\ a_{n-1} \end{pmatrix}$$ n = 1부터 반복적으로 곱해보면... $$ $$\begin{pmatrix} a_{2} \\ a_{1} \end{pmatrix}$$ = $$\begin{pmatrix} 1 & 1 \\ 1 & 0 \\ \end{pmatrix}$$ \begin{pmatrix} a_{1} \\ a_{0..

• format_list_bulleted 선형대수학 알고리즘
• · 2023. 3. 19.
• textsms

ABC 293 복기 E - Geometric Progression - 행렬곱 배우기 -

1. 문제 E - Geometric Progression (atcoder.jp) E - Geometric Progression AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 정수 A,X,M이 주어질 때, $$\sum_{k=0}^{X-1} A^{k}$$ 를 구하는 아주 간단한 문제 2. 풀이1 이미 재귀로 푸는 방법을 배운적 있다 컴퓨터가 등비수열의 합을 구하는 방법 (tistory.com) 컴퓨터가 등비수열의 합을 구하는 방법 1. 문제 15712번: 등비수열 (acmicpc.net) 15712번: 등비수열 첫째 줄에 a..

• format_list_bulleted Atcoder
• · 2023. 3. 12.
• textsms