탐색 범위를 줄여야하는 브루트포스 연습3 - 해밍 수열의 i번째 수 찾기

7868번: 해밍 수열 3개의 소인수 p1,p2,p3이 주어질 때 p1,p2,p3만으로 소인수를 가지는 자연수의 오름차순 배열에서 i번째 수를 찾는 문제 H(2,3,5)는 2,3,4,5,6,8,9,10,12,...  p1,p2,p3,i가 10^18보다 작다고 하니까 단순하게 다 돌려보는건 어려울것 같고 p1,p2,p3만을 소인수로 가지니까 H(p1,p2,p3)는 p1n1∗p2n2∗p3n3 여기서 출력하는 수가 10^18보다 작다고 하니까 결국 p1n1∗p2n2∗p3n3도 10^18보다 작아야함 따라서 n1,n2,n3  따라서 p1,p2,p3가 주어질때 0~59 * 0~59 * 0~59로 3중 for문 돌아보면서  p1**n1 * p2 ** n2 * p..

  • format_list_bulleted 브루트포스
  • · 2024. 11. 11.
  • textsms

탐색 범위를 줄여야하는 브루트포스 연습1 - 각 자릿수의 제곱합?

17755번: Równanie 정수 k가 주어질때 a  여기서 f(n)은 n을 10진법으로 표현했을 때 각 자릿수의 제곱합 k,a,b  이럴때는 탐색범위를 좁힐 수 있는지 생각해봐야한다  f(n)이 n을 10진법으로 표현했을 때 각 자릿수의 제곱합이므로,  n=a1∗10x1+a2∗10x2+a3∗10x3+...이므로  f(n)=a21+a22+....인데 여기서 $a_{i}  그런데 n이 최대 10^18이므로 f(n)이 최대가 될려면 999999999999999999로 9가 18개 있는경우이다. 이 경우 81*18 = 1458이라서 f(n)으로 가능한 값은 1부터 1458까지이다.  그러므로 ..

  • format_list_bulleted 브루트포스
  • · 2024. 10. 24.
  • 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진법으로 바꾸는 테크닉2 - n을 n번 이어붙인 정수

D - 88888888 (atcoder.jp) D - 88888888AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp  n을 n번 이어붙였을때, 그것을 998244353으로 나눈 나머지를 구하는 문제 숫자를 이어붙인 문제는... 한번 10진법으로 바꿔보면 해결법이 보이는 경우가 있다 https://deepdata.tistory.com/1235 문자열 수를 10진법으로 바꾸는 테크닉 - 배열에서 모든 가능한 순서쌍의 두 수를 이어붙여 만든D - Another Sigma Problem (atcoder.jp) D - Another..

  • format_list_bulleted 애드 혹 알고리즘
  • · 2024. 9. 8.
  • textsms

맨 위 정수가 주어질때, 아래 두 수의 합이 위 정수가 되는 피라미드 만들기

17802번: Integral Pyramid (acmicpc.net)  가장 위의 정수가 주어지고, 몇줄로 구성해야하는지 주어지고, 현재 정수 x는 바로 아래 줄의 2개의 정수 합으로 구성되도록 만든다. 현재 줄이 n개라면 아래 줄은 n+1개로 구성되어야한다. 예를 들어 15가 맨 위에 있고 3줄로 구성해야한다면  15 8 73 5 2 어떻게 할 수 있을까? 그냥 생각했을 때는 맨 위의 정수부터 시작해서 아래로 내려가도록 구성해야할 것 같다 맨 아래에서 위로 올라오기는 어려울 것 같다 이 말이지 그러면 맨 위의 정수를 절반으로 나눠서 15면 8과 7로 나누고... 8은 4와 4로 나눈 다음... 우측의 4와 7을 비교해서 7은 4와 3으로 나누고... 789를 6줄로 나누는 것도 789를 절반으로 해서 ..

  • format_list_bulleted 애드 혹 알고리즘
  • · 2024. 9. 6.
  • 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