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

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