BSGS

이산 로그 문제를 해결하기 위한 알고리즘으로, 주어진 a, b, p에 대해 a^n ≡ b (mod p)를 만족하는 최소의 양의 정수 n을 찾는 데 사용됩니다.

알고리즘 절차

이 문제는 두 가지 경우로 나눌 수 있습니다:

일반 BSGS

a와 p가 서로소(a⊥p)인 경우입니다.

이 경우 a는 역원을 가지며, BSGS는 이 성질을 이용해 제곱근 시간 알고리즘을 설계합니다.

a^n의 주기 길이는 φ(p)이므로, 0 ≤ n < φ(p)임을 알 수 있습니다(오일러 정리). 여기서 s = √φ(p)로 설정하면, n은 n = k×s + c (0 ≤ c < s)로 표현할 수 있습니다.

이는 광속제곱과 유사한 개념입니다. 먼저 모든 a^c를 계산하고, k를 순회하면서 최소의 c를 찾아야 합니다. 이때 a^(k×s)의 역원이 필요하며, 해시 테이블을 사용하면 O(√p) 시간에 해결할 수 있습니다.

하지만 역원 계산이 추가적인 로그 시간을 요하므로, n을 k×s - c로 다시 표현하여 b×a^c = a^(k×s) 형태로 만들 수 있습니다. 이 경우 해시 테이블에 b×a^c를 저장하고 최대의 c를 찾으면 됩니다.

exBSGS

이는 a와 p가 반드시 서로소가 아닌 경우를 다룹니다. 즉, a가 역원을 가지지 않는 경우입니다.

동일식의 성질을 이용하여 a, b, p를 gcd(a,p)로 나눌 수 있습니다. a는 여러 제곱을 가질 수 있으므로, 한 번의 나눗셈으로는 충분하지 않으며 a가 모수와 서로소가 될 때까지 나누어야 합니다. 이는 a^(c+x) 형태로 표현될 수 있으며, 여기서 c는 상수입니다. 따라서 a^1부터 a^x까지는 별도로 처리해야 합니다. 나누는 과정에서 gcd(a,p)가 b를 나눌 수 없으면 무해결(no solution)임을 판단합니다.

적용 분야

a가 정수인 경우

대부분 이산 로그 문제를 해결하는 데 사용됩니다.

a가 행렬인 경우

a는 정수일 필요가 없으며, 행렬 등 다른 형태일 수도 있습니다.

하지만 행렬을 사용할 때는 반드시 역행렬이 존재해야 합니다. 역행렬 존재 여부는 행렬식으로 판단할 수 있지만, 고차원에서는 적용이 어려울 수 있습니다. 대부분의 경우 문제 조건에 따라 직접 분석 판단해야 합니다.

따라서 수열을 재귀적으로 정의하거나 기타 특수한 연산을 수행할 때도 BSGS의 아이디어를 적용할 수 있습니다.

Miller_Rabin

본질

페르마 소수 검사와 2차 탐정 정리를 사용합니다.

이름에서 알 수 있듯이, 먼저 페르마 소수 검사로 소수를 판별합니다. 구체적으로, 현재 검사 중인 소수를 p라고 할 때, 만약 ∃a, a^(p-1) ≢ 1 (mod p)라면 p는 반드시 소수가 아닙니다.

하지만 이 검사는 모든 소수를 커버할 수 없으므로, 2차 탐정 정리를 사용하여 이 결함을 보완합니다.

2차 탐정 정리는 다음과 같습니다: 만약 p가 소수라면, x^2 ≡ 1 (mod p)의 해는 x=1과 x=p-1 두 가뿐입니다.

이 두 가지 방법을 사용하여 소수를 판별할 수 있습니다. 페르마 검사에서 a는 고정되지 않지만, 처음 12개의 소수를 a로 사용하면 p ≤ 10^18인 모든 소수를 성공적으로 검출할 수 있습니다.

시간 복잡도는 O(T×log²n)이며, 여기서 T는 검사 횟수입니다.

코드

템플릿 코드

적용

소수 판별. Pollard_rho 알고리즘에서도 사용됩니다.

Pollard_rho

n ≤ 10^18인 수의 소인수분해는 어떻게 할까요?

Pollard_rho 알고리즘을 사용합니다.

2차 잉여

정확히 무엇인가요?

피보나치 수열의 주기

일반항 공식은 무엇인가요?

디리클레 컨볼루션

디리클레 컨볼루션은 수론에서 비교적 유용한 보조 도구입니다.

기초 지식

정의

h = f*g로 설정할 때, 여기서 *는 디리클레 컨볼루션 기호입니다.

h(i) = Σ(d|i) f(d)×g(i/d)

여러 함수의 컨볼루션은 다음과 같이 표현할 수 있습니다:

만약 h = f₁f₂f₃...fₖ₋₁*fₖ 라면,

h(n) = Σ(d₁×d₂×d₃...dₖ₋₁×dₖ=n) f₁(d₁)×f₂(d₂)×f₃(d₃)...×fₖ₋₁(dₖ₋₁)×fₖ(dₖ)

디리클레 컨볼루션에서 항원(identity element)은 ε(n) = [n=1]이며, 즉 f*ε = f 입니다.

그리고 f(1) ≠ 0이면, g*f = ε를 만족하는 g가 존재하며, 이를 f의 역원이라고 하며 f⁻¹로 표기할 수 있습니다.

특히, 1(n) = 1의 역원은 μ이며, 즉 1*μ = ε이고, 이것이 바로 뫼비우스 반전이며 뒤에서 다룰 것입니다.

일부 성질

정의에서 쉽게 디리클레 컨볼루션이 교환법칙, 결합법칙, 분배법칙을 만족함을 알 수 있습니다.

곱성 함수와 곱성 함수의 디리클레 컨볼루션은 곱성 함수입니다.

이 점은 매우 중요하며, 이후의 많은 문제/체 알고리즘에서 사용됩니다. 특히 PN 체에서 이 점을 잊어버려 복잡도가 증가하는 경우가 많습니다.

계산 방법

명백히, 약수를 열거하여 O(n×√n)으로 계산할 수 있지만, 분명히 O(n×log n)으로 최적화할 수 있습니다.

동시에, f와 g가 주어졌을 때 h = f/g = f*g⁻¹을 O(n×log n)으로 계산할 수 있습니다.

구체적으로, 다음 식으로 변형할 수 있습니다:

f(i) = Σ(d|i) h(d)×g(i/d)

i=1을 대입하면 h(1) = f(1)/g(1)을 얻습니다.

마찬가지로, i ≥ 2인 h(i)에 대해 재귀적 과정을 고려합니다. 현재 h(1) ~ h(i-1)는 이미 계산되었으므로, d=i를 별도로 분리하면 다음을 얻을 수 있습니다:

f(i) = h(i)×g(1) + Σ(d|i, d 1일 때 기여가 없으므로, n' = p₁×p₂...×p_k로 설정합니다.

Σ(d|n) μ(d) = Σ(d|n') μ(d) = Σ(i=0 to k)(-1)^i×C(k,i) = (-1+1)^k

k=0, 즉 n=1일 때 위 식은 1이며, 그 외의 모든 경우에는 0이므로 증명됩니다.

사용 방법

1*μ = ε이므로, 가장 일반적이고 유용한 형태는 [...=1]을 제거하는 것입니다.

예를 들어, [gcd(a,b)=1]은 뫼비우스 반전을 사용하여 Σ(d|gcd(a,b)) μ(d) = Σ(d|a,d|b) μ(d)로 변환할 수 있습니다. 이 경우 일반적으로 d를 열거하고 여러 연산을 수행합니다.

예를 들어, 다음을 구한다고 가정합시다:

Σ(i=1 to n) Σ(j=1 to m) [gcd(i,j)=k]

먼저, =k가 번거롭습니다. gcd(i,j)=k라면 i,j는 반드시 k의 배수여야 하므로, k를 인수분해할 수 있습니다.

Σ(i=1 to ⌊n/k⌋) Σ(j=1 to ⌊m/k⌋) [gcd(i×k,j×k)=k] = Σ(i=1 to ⌊n/k⌋) Σ(j=1 to ⌊m/k⌋) [gcd(i,j)=1]

이는 표준 모델이 됩니다.

Σ(i=1 to ⌊n/k⌋) Σ(j=1 to ⌊m/k⌋) [gcd(i,j)=1] = Σ(i=1 to ⌊n/k⌋) Σ(j=1 to ⌊m/k⌋) Σ(d|i,d|j) μ(d)

그리고 합산 순서를 바꾸면:

Σ(i=1 to ⌊n/k⌋) Σ(j=1 to ⌊m/k⌋) Σ(d|i,d|j) μ(d) = Σ(d=1 to n) μ(d) ⌊n/(k×d)⌋ ⌊m/(k×d)⌋

그런 다음 정수 나누기 블록을 사용할 수 있지만, 두 개의 숫자가 있습니다? 함께 사용하세요!

int r=1;
for(int i=1;i<=min(x,y);i=r+1){
  r=min(x/(x/i),y/(y/i));
}

위에서 언급한 것들은 비교적 기초적인 뫼비우스 반전 문제이며, 일부 더 복합적인 예제는 배제 등 고급 사고방식이 필요합니다. 뫼비우스 함수 자체가 유사 배제 계수이며, 특히 소인수와 관련된 배제에서 (-1)^k는 매우 익숙하게 느껴집니다.

다음은 고전적인 예제입니다:

1 ~ n 사이에서 d>1, d² ∤ x인 x의 개수를 구하세요.

우리는 조건을 만족하는 d의 최댓값을 dmax라고 가정하면, 위 식은 다음과 같이 다시 작성할 수 있습니다:

Σ(i=1 to n) [dmax_i=1] = Σ(i=1 to n) Σ(d|dmax_i) μ(d) = Σ(i=1 to n) Σ(d²|i) μ(d)

그리고 합산 순서를 바꾸면:

Σ(i=1 to n) Σ(d²|i) μ(d) = Σ(d=1 to √n) μ(d) × ⌊n/d²⌋

그런 다음 정수 나누기 블록을 적용하면 됩니다. 이는 본질적으로 배제를 수행하는 것입니다.

선형 체 아래의 알고리즘

두 자오 체 (Du Jiao sieve)

아이디어

아이디어는 비교적 간단하지만, 일반적으로 일반적인 곱성 함수의 접두사 합을 계산하는 데 사용됩니다.

필터링하려는 함수를 s(n) = Σ(i=1 to n) f(i)라고 가정하며, 여기서 f는 곱성 함수입니다.

핵심 아이디어는 h = f*g를 구성하는 것입니다. 여기서 g와 h는 모두 쉽게 계산할 수 있습니다.

s(i) = Σ(i=1 to n) f(i)로 설정하고, 우리는 방금 언급한 아이디어를 시도해 봅시다:

Σ(i=1 to n) h(i) = Σ(i=1 to n) Σ(d|i) f(d)×g(i/d) = Σ(i=1 to n) Σ(d|i) f(i/d)×g(d)

그리고 합산 순서를 바꿉니다:

= Σ(d=1 to n) g(d) Σ(i=1 to ⌊n/d⌋) f(i) = Σ(d=1 to n) g(d) × s(⌊n/d⌋)

그런 다음 식에 마법처럼 s가 나타나는 것을 발견합니다. d=1을 별도로 분리하고 이항하면 다음을 얻을 수 있습니다:

Σ(i=1 to n) h(i) = g(1) × s(n) + Σ(d=2 to n) g(d) × s(⌊n/d⌋)

g(1) × s(n) = Σ(i=1 to n) h(i) - Σ(d=2 to n) g(d) × s(⌊n/d⌋)

그런 다음 이것이 재귀적으로 계산될 수 있음을 발견합니다!

예시

몇 가지 예시를 들어 봅시다:

s₁(n) = Σ(i=1 to n) μ(i), s₂(n) = Σ(i=1 to n) φ(i)를 계산합니다.

먼저 μ를 어떻게 계산할지 생각해 봅시다. 두 자오 체의 아이디어에 따라, 우리는 h = μ*g를 구성할 수 있습니다. 뫼비우스 반전에 따라, g(n) = 1을 구성하는 것이 어렵지 않다는 것을 알 수 있습니다. 이렇게 하면 h(n) = [n=1]이 되어 매우 편리합니다.

그 다음 위 공식을 적용하면:

s₁(n) = 1 - Σ(d=2 to n) s₁(⌊n/d⌋)

그러면 비교적 쉽게 계산할 수 있습니다.

μ를 계산하는 방법을 알면 φ도 마찬가지입니다. 마찬가지로, 오일러 반전에 따라 우리는 여전히 g(n) = 1을 구성합니다. 그러면 h(n) = n가 되어 마찬가지로 비교적 쉽게 계산할 수 있습니다:

s₂(n) = n×(n+1)/2 - Σ(d=2 to n) s₁(⌊n/d⌋)

이 두 가지는 비교적 기초적이며, 다음은 약간 더 어려운 예시입니다:

s₃(n) = Σ(i=1 to n) d(i)를 계산합니다.

여기서 d(i)는 i의 약수의 개수를 의미합니다.

어떻게 구성할까요?

아, g = μ로 구성하면 됩니다!

μ(1) × s₃(n) = n - Σ(d=2 to n) μ(d) × s₃(⌊n/d⌋)

μ를 계산해야 하나요? 마찬가지로 두 자오 체를 사용하며, 사용되는 μ는 모두 n의 정수 나누기 블록 내의 수이므로, 사실상 s₁(n)을 한 번 체하는 것과 같습니다.

고급 예시

그렇다면 다음을 계산한다면:

s₄(n) = Σ(i=1 to n) i^k × μ(i), s₅(n) = Σ(i=1 to n) i^k × φ(i)

직접 어떤 것을 컨볼루션에 넣기 어렵다는 것을 발견하지만, 이 두 가지 합산은 매우 표준적입니다. 오일러 반전과 뫼비우스 반전에 따라 이들은 약수 함수에 대한 합 후 매우 쉬워집니다. 그리고 디리클레 컨볼루션 자체가 약수 형태를 가지고 있으므로, i^k를 분리하면 반전할 수 있습니다.

그러면 답은 자연스럽게 나옵니다. id^k를 컨볼루션하세요!

Σ(i=1 to n) h₄(n) = Σ(i=1 to n) Σ(d|i) d^k × μ(d) × (i/d)^k = Σ(i=1 to n) i^k Σ(d|i) μ(d)

그 다음 이것이 뫼비우스 반전임을 발견합니다:

Σ(i=1 to n) h₄(n) = Σ(i=1 to n) i^k

이는 멱합(power sum) 형태이므로 비교적 쉽게 계산할 수 있으며, 다음을 얻습니다:

s₄(n) = Σ(i=1 to n) i^k - Σ(d=2 to n) d^k × s₄(⌊n/d⌋)

s₅도 마찬가지로 id^k를 컨볼루션하며, 앞의 추론 과정은 유사하지만 오일러 반전이 됩니다:

Σ(i=1 to n) h₅(n) = Σ(i=1 to n) i^k Σ(d|i) φ(d) = Σ(i=1 to n) i^k × i = Σ(i=1 to n) i^(k+1)

s₅(n) = Σ(i=1 to n) i^(k+1) - Σ(d=2 to n) d^k × s₅(⌊n/d⌋)

시간 복잡도

다음은 비교적 중요한 것입니다: 복잡도는 얼마나 될까요? 재귀적 복잡도는 분석하기 어렵기 때문에, 메모이제이션 후의 복잡도를 고려합니다:

T(n) = Σ(i=1 to √n) O(√n) + Σ(i=1 to √n) O(√(n/i))

그 다음 적분이 필요하며, 저는 적분을 잘하지 못하므로 결론만 말씀드리겠습니다: T(n) = O(n^(3/4))입니다.

그러다 실제로 우리는 일부 s_i를 사전 처리할 수 있음을 발견합니다. 임계값 T를 설정하고, O(T)로 1 ~ T의 s를 처리합니다. T보다 큰 부분은 재귀적으로 처리하면 다음과 같이 됩니다:

Σ(i=1 to ⌊n/T⌋) O(√(n/i)) = O(n/√T)

그러면 두 부분을 합치면 O(T + n/√T)가 되며, T = n^(2/3)일 때 복잡도는 O(n^(2/3))가 됩니다. (물론 이것도 적분을 통해 도출됩니다.)

요약

핵심은 h = f*g를 구성하는 것입니다. 여기서 h와 g는 쉽게 구할 수 있어야 합니다. 일부 고전적인 예시는 위 이미지에 있습니다. 그리고 id^k를 컨볼루션하는 기술도 있습니다.

PN 체 (Powerful Number sieve)

Powerful Number!

이 체 알고리즘은 곱성 함수의 접두사 합을 체하지만, 일정한 제한이 있으며 단일 호출만 가능합니다.

아이디어

이 체 알고리즘은 다음 사실에 기반합니다:

Powerful Number(거듭제곱수)를 x = p₁^r₁×p₂^r₂×p₃^r₃...×p_k^r_k 형태로 정의할 때, 여기서 r_i ≥ 2입니다. 그러면 n 이내의 Powerful Number의 개수는 O(√n) 수준입니다.

다음은 증명입니다:

임의의 x는 x = a²×b³ 형태로 표현할 수 있습니다. 계수를 고려하면, cnt = Σ(a=1 to √n) ⌊³√(n/a²)⌋이며, 이를 적분하면 cnt = O(√n)을 얻을 수 있습니다.

거듭제곱수의 수를 바탕으로, 거듭제곱수 체는 거듭제곱수에서만 값이 존재하는 함수 h를 구성하려고 시도합니다. 즉, 비거듭제곱수에서는 모두 0입니다. 이는 h(p) = 0, p ∈ Prime와 동일함을 쉽게 알 수 있습니다.

h가 f와 어떻게 관련되면서 위 조건을 만족할 수 있을까요? 다음이 매우巧妙합니다!

g(p) = f(p), p ∈ Prime이고, g가 곱성 함수가 되도록 함수 g를 구성해 봅시다.

f = g*h로 설정하면 놀라운 일이 발생합니다! 소수에서의 값을 고려합니다:

f(p) = g(1)×h(p) + g(p)×h(1)

g가 곱성 함수이므로 g(1) = 1이며, 앞서 강조했듯이, h = f*g⁻¹ 역시 곱성 함수입니다. 따라서 h(1) = 1이며, 이를 대입하면 놀라운 발견을 합니다:

f(p) = 1×h(p) + g(p)×1 → h(p) = 0

모든 위 조건이 만족됩니다!!!

그 다음 우리는 식을 추론합니다:

Σ(i=1 to n) f(i) = Σ(i=1 to n) Σ(d|i) h(d)×g(i/d) = Σ(d=1 to n) h(d) Σ(i=1 to ⌊n/d⌋) g(i)

쉽게 알 수 있듯이, 우리는 실제로 O(√n) 위치의 값만 계산하며, g의 접두사 합이 필요합니다.

1 ~ n 이내의 모든 거듭제곱수를 어떻게 알 수 있을까요?

직접 p_i^r_i 형태로 탐색할 수 있지만, 상태를 상속할 수 없어야 합니다. 즉, 탐색 시마다 x는 커져야 합니다. 그렇지 않으면 연속된 유효한 ×1이 복잡도를 폭발시킬 것입니다.

그 다음 h를 계산하는 방법을 고려해 봅시다. 이미 p_i^r_i를 열거하고 있습니다. O(√n×log n) 시간 복잡도로 모든 h(p^k)를 계산할 수 있으며, 그 후 곱하면 됩니다. h(p^k)를 계산하는 것은 앞서 언급된 재귀를 사용하면 됩니다.

하지만 g가 단순하지 않은 곱성 함수라면, 복잡도의 병목은 g의 접두사 합 계산에 있을 수 있습니다.

하지만 g의 접두사 합이 O(1)로 계산 가능하다면, PN 체의 속도 이점이 비교적 명확해집니다.

예시

고전적인 예제

먼저 몇 가지 간단한 추론을 하면, 문제가 다음을 요구함을 발견합니다:

x = p_i^r_i, r_i > 0일 때, s(x) = p_i^(r_i-1)로 설정합니다.

Σ(i=1 to n) f(i) = Σ(i=1 to n) i/d(i/s(i)) = Σ(i=1 to n) i/Π(Π p_j^r_j = i) r_j

마법처럼 이 함수가 곱성 함수임을 발견합니다. 그리고 f(p) = p입니다. 따라서 PN 체를 사용할 수 있으며, g는 명백히 id와 같습니다.

그 다음 식을 작성합니다:

Σ(i=1 to n) f(i) = Σ(d=1 to n) h(d) × ⌊n/d⌋ × (⌊n/d⌋+1)/2

그 다음 이 식이 매우 간결하며, PN 체의 이론적 최적 복잡도에 도달합니다!

요약

f(p) = g(p)를 만족하는 곱성 함수 g를 찾을 수 있다면, PN 체를 사용할 수 있습니다. 그 다음 h(p^k)를 사전 처리하고, 탐색 시 곱하여 h(x)를 얻습니다. (하지만 일반적으로 g가 비교적 단순할 때만 쉽게 할 수 있습니다.)

민-25 체 (Min-25 sieve)

좋은 도구이며, 거의 모든 곱성 함수를 체할 수 있습니다.

소수점 값 체

먼저 f(p) = 1을 어떻게 처리할지 생각해 봅시다. 즉, 소수 개수를 체합니다.

에라토스테네스 체 과정을 고려하면, G(n,i)는 i번째 에라토스테네스 체 후에 남아 있는 개수를 나타냅니다.

이것이 dp와 유사하게 보입니다. G(n,i-1)에서 전이하는 것을 고려하면, 빠지는 개수는 i번째 체에서 제거된 개수입니다. ⌊n/prime_i⌋은 명백히 중복 계산됩니다. 왜냐하면 우리는 prime_i가 가장 작은 소인수임을 보장해야 하기 때문입니다.

prime_i보다 크거나 같은 최소 소인수를 가지는 ⌊n/prime_i⌋의 개수를 계산해야 한다는 것을 쉽게 알 수 있습니다.

마법 같은 일이 발생합니다! 이것이 하위 문제이며, 그 값은 G(⌊n/prime_i⌋, i-1)입니다. 하지만 여기에는 prime_1 ~ prime_i-1도 포함되어 있으므로, 빼주면 됩니다.

다음 식을 얻습니다:

G(n,i) = G(n,i-1) - [G(⌊n/prime_i⌋, i-1) - (i-1)]

이 식은 재귀적으로 계산할 수 있으며, 복잡도를 분석해야 합니다.

우리는 √n 이내의 소수만 열거하면 되므로, 총 시간 복잡도는 다음과 같습니다:

T(n) = Σ(i=1 to √n) O(√i/log √i) + Σ(i=1 to √n) O(√(n/i)/log √(n/i))

그런 다음 확장과 적분을 통해 약 O(n^(3/4)/log n)이 됩니다.

직접 구현하면 상수가 비교적 크므로, 배열을 롤링 계산할 수 있습니다. ⌊n/prime_i⌋는 O(√n) 종류의 값을 가지므로, 두 개의 배열을 매핑하여 기록할 수 있습니다.

일부 상수 최적화 세부 사항은 다음과 같습니다:

for(int i=1;i<=cnt;i++){
    while(now>0&&b[now]<prime[i]*prime[i]){
        now--;
    }
    for(int j=1;j<=now;j++){
        int noww=b[j]/prime[i];
        g[j]-=(noww>=prime[i-1])?((g[noww<=len?id1[noww]:id2[n/noww]])-(i-1)):0;
    }
}

모든 수의 접두사 합 체

주의해야 할 것은, 반드시 일반적인 함수가 아닐 수 있다는 것입니다. 만약 함수 계산이 소인수 지수와 관련된 식으로 변환될 수 있다면, 마찬가지로 계산할 수 있습니다.

S(n,i)는 2 ~ n에서 최소 소인수 > prime_i인 값의 합을 나타냅니다.

계산 방법을 고려해 봅시다.

최소 소인수를 열거하여 계산하는 것이 자연스럽습니다:

S(n,i) = Σ(x=i+1 to cnt) Σ(j=1 to prime_x^j ≤ n) f(prime_x^j) × S(⌊n/prime_x^j⌋, x)

만약 Σ(i=1 to n) d(i)를 계산한다면 다음과 같습니다:

S(n,i) = Σ(x=i+1 to cnt) Σ(j=1 to prime_x^j ≤ n) (j+1) × (S(⌊n/prime_x^j⌋, x) + [j≠1])

하지만 실제 테스트하면 이것이 매우 느리다는 것을 발견합니다. 왜냐하우 우리는 모든 prime_i ~ n에서 소수점 값을 다시 계산하기 때문입니다. 이전 소수 개수 체 부분에서 소수점 값은 실제로 비교적 쉽게 계산될 수 있음을 발견했으며, 따라서 √n 이내의 소수만 열거하면 됩니다.

S(n,i) = G(n) - G(prime_i) + Σ(x=i+1 to x≤cnt, prime_x^2≤n) Σ(j=1 to prime_x^j ≤ n) (j+1) × (S(⌊n/prime_x^j⌋, x) + 1)

그러면 시간 복잡도는 O(n^(3/4)/log n)이 됩니다. 하지만 일반 사용에서 재귀적으로 직접 작성하면 10^9 ~ 10^12 범위에서도 매우 빠르게 실행되므로, 메모이제이션할 필요가 없습니다.

업데이트 2025.6.21

민-25 시험을 보고, 이전에 모든 점 값의 합을 체하지 않았다는 것을 발견했습니다. 따라서 보충하며, 이제 알게 되었습니다.