배열의 모든 수의 쌍의 곱의 합을 O(N)에 구하는 방법

https://atcoder.jp/contests/abc177/tasks/abc177_c C - Sum of product of pairsAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 크기 N인 배열 $A_{1}, A_{2}, ..., A_{N}$이 주어진다. 이때, 이 배열의 가능한 모든 인덱스 쌍 (i,j)에 대해 $A_{i} * A_{j}$의 합을 어떻게 구할까? 여기서 i 가장 쉽게 생각할 수 있는 방법은 당연히 모든 인덱스 쌍을 순회해서 구하는 $O(N^{2})$방법이다. n = int(input())A =..

  • format_list_bulleted 대수학
  • · 2026. 8. 17.
  • textsms

프로베니우스의 동전 문제(Frobenius coin problem)와 슈어의 정리(Schur's theorem)

1. 프로베니우스의 동전 문제(Frobenius coin problem) 서로 다른 두 동전 x원, y원이 있을때, 이 두 동전을 각각 적당한 개수를 사용하여, 만들 수 없는 금액중 가장 큰 값은? 이 문제의 정답을 프로베니우스의 수(Frobenius number)라고 부른다. 예를 들어 3원, 5원짜리 동전으로 만들 수 없는 가장 큰 금액은 7원이다. 이 말은 8원 이상의 금액은 무조건 만들 수 있다는 뜻이다. 주의할 점은 7원 밑의 금액 중에서 1,2,4원은 만들 수 없다는 것은 자명하다. 프로베니우스의 수는 x,y가 서로소(최대공약수가 1)일때만 존재한다. 이때, 프로베니우스의 수는 xy - x - y임이 알려져있다. 2. 일반화된 문제 일반적으로는, n개의 동전 $a_{1}, a_{2},...,..

  • format_list_bulleted 정수론
  • · 2026. 3. 30.
  • textsms
Prime number Theorem으로 알아보는 구간 내의 소수 개수

Prime number Theorem으로 알아보는 구간 내의 소수 개수

1. prime number theorem(소수 정리) 양의 실수 x 이하에 존재하는 소수의 개수를 $\pi(x)$라고 한다면 다음이 성립한다. 양수 x이하의 소수의 개수는 근사적으로 x/logx개라는 소리다. 로그 적분 함수 li(x)는 다음과 같이 정의한다. 그래프가 다음과 같다. 구간 [0,x]가 아닌 [2,x]에서 로그 적분 함수를 Li(x)로 나타내기도 한다 이를 이용해서 다음과 같이 나타내기도 한다. 즉, $\pi(x)$는 Li(x)에 근사할 수 있고, 현대에는 이게 더 정확하다고 알려져있다. 2. 소수의 밀도 직관적으로 큰 숫자에서 소수 사이 간격이 점점 커진다는 것을 알 수 있다. 에라토스테네스의 체로 구해보면 알수 있다 그렇게 차이나지는 않네 흠.. 양수..

  • format_list_bulleted 정수론
  • · 2025. 7. 2.
  • textsms
에라토스테네스의 체 변형 segmented sieve 배우기

에라토스테네스의 체 변형 segmented sieve 배우기

https://deepdata.tistory.com/393 소수를 빠르게 구하는 에라토스테네스의 체 알고리즘1. 소수를 구하는 방법 컴퓨터가 주어진 수 n이 소수인지 판단할려면 어떻게 해야할까? 1부터 n까지 n에 나눠보면서 n의 약수인지 아닌지 판단해보면 된다. n의 약수가 1과 n만 있어야 n이 소수이다deepdata.tistory.com 에라토스테네스의 체의 문제는 수행하는 연산의 수가 아니라 메모리 요구량에 있다. n이 매우 큰 경우, 소수의 범위가 메모리에 모두 담기지 않을 수 있다. 더 나쁜 것은, n이 그리 크지 않은 경우에도 캐시 사용이 매우 비효율적이라는 점이다. 이 알고리즘은 배열 A 전체를 순차적으로 탐색하며, 참조 지역성이 거의 없다. 이러한 문제에 대한 해결책으로 분할 체(se..

  • format_list_bulleted 정수론
  • · 2025. 6. 30.
  • textsms
AtCoder Beginner Contest 405 대충 복기(BFS, 최단경로, 경우의수, 팩토리얼 모듈로 역원)

AtCoder Beginner Contest 405 대충 복기(BFS, 최단경로, 경우의수, 팩토리얼 모듈로 역원)

1. D번 D - Escape Route D - Escape RouteAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 2차원 배열이 주어질때, 각 위치에서 탈출구 E번까지 가는 최단 경로를 표시해야하는 문제 #은 이동불가능 지역이므로 표시하지 않는다. ..E...이라고 한다면? >>E>>^ 이런식으로 될 것이다. 혹은 정답이 여러개일 수 있는데 >>E^>^도 정답이 될듯? 각각의 지점에서 E까지 가는 최단 경로를 어떻게 찾는다고 하더라도 표시를 어떻게 해야하지? 각각의 지점이 1000*1000개인데 이걸 언제 다하냐? 그..

  • format_list_bulleted 경쟁 프로그래밍/Atcoder
  • · 2025. 5. 11.
  • textsms
의외로 모르는 어떤 분수가 유한소수가 될 수 있는 조건

의외로 모르는 어떤 분수가 유한소수가 될 수 있는 조건

1. 유한소수? 유한소수는 소숫점 아래에 있는 수가 유한한 소수이다. 어떤 분수가 유한소수일려면 기약분수로 나타내고, 분모를 소인수분해 했을때, 2나 5만을 인수로 가져야한다. 왜냐하면, 유한소수는 (정수).xxxxxxx 형태로, 정수 + 0.xxxxxxx로 나타낼 수 있다. 이때, 0.xxxxxxxx = xxxxxxxxx/10^n이므로, (y + xxxxxxxxxx)/10^n형태로 나타난다. 따라서, 유한소수를 기약분수로 나타내 분모를 소인수분해해보면 반드시 2나 5만을 인수로 가진다. 2. 연습문제 https://atcoder.jp/contests/agc047/tasks/agc047_a A - Integer ProductAtCoder is a programming contest site for an..

  • format_list_bulleted 정수론
  • · 2025. 4. 29.
  • textsms