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

15319번: 동혁이의 생일선물 정수 x의 거듭제곱 x0,x1,x2,...에 대하여 이들의 모든 부분집합 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
나눗셈 실수오차가 생긴다면 직접 나눗셈을 구현하기

나눗셈 실수오차가 생긴다면 직접 나눗셈을 구현하기

1206번: 사람의 수 (acmicpc.net)  n명의 사람이 0점부터 10점까지 정수로 존재하는 설문조사 문항에 점수를 내서 각 문항마다 평균을 낸 점수가 실수로 주어질때, n이 될 수 있는 가장 작은 정수를 구하는 문제 평균이 소수점 셋째자리까지만 주어진다 예를 들어 32/106 = 0.3018867924528302... 인데 0.301만 주어지는 ---------------------------------------------------------------------------------------------------------------------------------- 만약 설문조사한 사람 수가 x명이고 i번째 문항의 점수 합이 v이면 vx≈A[i] A..

  • format_list_bulleted 정수론
  • · 2024. 9. 26.
  • textsms
10진수를 다른 진법으로 바꾸는 방법

10진수를 다른 진법으로 바꾸는 방법

1. 1보다 큰 10진수를 다른 진수로 변환하는 방법 주어진 수를 변환하고자하는 진수의 base로 계속 나누고 나머지를 써둔다 마지막에 저장해둔 나머지 뒤에서부터 가지고옴 예를 들어 133은 3진법으로 변환하면 11221(3)이다.   2. 10진수 소수를 진수 바꾸는 방법 반면 소수는 방법이 조금 다른데 base를 계속 곱해나간 뒤 소수점을 넘은 정수는 옆에 따로 저장해두고 정수를 뺀 나머지를 다음 단계로 보낸 뒤 base를 계속 곱해 다음 단계로 보낸 나머지 부분이 0이 될때까지 반복함 정수 변환은 맨 뒤에서부터 앞으로 가지고 왔지만 맨 처음부터 따로 저장한 수를 맨 뒤까지 가지고 오면 끝 예를 들어 0.375는 8진수로 변환하면 0.3(8)이고 0.1을 2진수로 변환하면 $0.00..

  • format_list_bulleted 정수론
  • · 2024. 9. 1.
  • textsms

2^30으로 나눈 나머지로 2^5으로 나눈 나머지를 구할 수 있을까

8672번: Drabina (acmicpc.net) 사다리의 맨 끝단 s까지 올라가는데 한걸음 혹은 두걸음씩 올라갈 수 있다 이 때 끝까지 올라가는 방법의 수를 2p로 나눈 나머지를 구해야한다. 이것만 보면 매우 쉬운 문제다 dp[i] = i번째까지 올라가는 방법의 수하면 가능한 경우는 한걸음 혹은 두걸음이므로... dp[i] += dp[i-1]dp[i] += dp[i-2] 인 전형적인 문제 dp = [0]*(s+1)dp[0] = 1mod = 2**pfor i in range(1,s+1): for j in range(1,3): if i >= j: dp[i] += (dp[i-j]) dp[i] %= mod  문제는 최대 ..

  • format_list_bulleted 정수론
  • · 2024. 8. 10.
  • textsms

골드바흐의 추측을 이용해 정수 n을 k개의 소수 합으로 표현하기

25309번: K개의 소수 (acmicpc.net) 정수 n을 k개의 소수 합으로 표현하라는 문제 여기서 핵심은 서로 다른 k개의 소수가 아니라, 같은 소수를 사용해도 좋다. 그리고 문제는 n이 최대 108이고 k는 최대 10000이라 단순한 방법으로는 어렵다 먼저 생각할 수 있는 것은 가장 작은 소수가 2이기 때문에, 2를 k개 사용하여 2k가 만들 수 있는 정수의 최솟값이다. 따라서 n = 2k이면 일단 분해하는 것이 가능하다. n,k = map(int,input().split())if n   만약 k = 1이면 n 자체로 소수인지 아닌지 판단하면 된다.  O(√n)에 소수 판단할 수 있다. def is_prime(n): for i in range(2,int(n**..

  • format_list_bulleted 정수론
  • · 2024. 5. 24.
  • textsms

약수를 세는 것보다 배수를 세는 것이 더 쉽다(홀수인 약수의 합, 유일한 소인수의 개수를 구하는 방법)

SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 어떤 정수 x의 약수 중 홀수인 약수의 합을 f(x)라고 할때, L,R이 주어지면 L이상 R이하의 모든 x에 대해 f(x)의 합을 구하는 문제 단순한 방법으로는 소인수분해를 해서 홀수인 소인수들의 곱으로 약수의 합을 구하면 된다. https://deepdata.tistory.com/588 약수의 합과 약수의 개수 공식 익히기 1. 약수의 개수 자연수 n의 소인수분해가 n=px11px22...pxkk라고 한다면, n의 양의 약수의 개수는 $$d(n) = (x_{1}+1)(x_..

  • format_list_bulleted 정수론
  • · 2024. 4. 11.
  • textsms