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

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

약수의 합과 약수의 개수 공식 익히기

1. 약수의 개수 자연수 n의 소인수분해가 $$n = p_{1}^{x_{1}}p_{2}^{x_{2}}...p_{k}^{x_{k}}$$ 라고 한다면, n의 양의 약수의 개수는 $$d(n) = (x_{1}+1)(x_{2}+1)...(x_{k}+1)$$ n을 소인수분해하여, 소인수들의 지수 + 1의 곱의 합이 약수의 개수이다. 1-1) 간단한 증명 왜냐하면 n의 약수는 $p_{1}, p_{2}, ... , p_{k}$들의 곱으로 이루어져 있는데, 각각은 $x_{1}, x_{2}, ... , x_{k}$개씩 사용할 수 있다. 따라서 곱의 법칙에 의해 모든 경우의 수는 $p_{1}, p_{2}, ... , p_{k}$을 각각 (0,1,2,...,$x_{1}$), (0,1,2,...,$x_{2}$), ... , (0..

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

컴퓨터가 등비수열의 합을 구하는 방법

1. 문제 15712번: 등비수열 (acmicpc.net) 15712번: 등비수열 첫째 줄에 a, r, n, mod가 공백으로 구분되어 주어진다. a, r, n, mod는 모두 1보다 크거나 같고, 109보다 작거나 같은 자연수이다. www.acmicpc.net 초항이 a, 공비가 r, 항 수가 n인 등비수열의 합을 mod로 나눈 나머지를 구하는 간단한 문제 초항이 a이고 공비가 r이며 항 수가 n인 등비수열의 합은.. 공비 r이 1이 아니면, $$S = a \times \frac{r^{n}-1}{r-1}$$ 이라는 아주 쉬운 공식이 있고 이거에 따라 계산해서 mod로 나눈 나머지 구하면 되는거 아니냐 라고 쉽게 생각하면 이 문제는 풀수가 없다 a,r,n이 작으면 상관 없겠지만... 매우 크면 $r^{n..

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