Problem 401 : Sum of squares of divisors (25%)

Description

original

The divisors of 6 are 1,2,3 and 6. The sum of the squares of these numbers is 1+4+9+36=50.

Let sigma2(n) represent the sum of the squares of the divisors of n. Thus sigma2(6)=50.

Let SIGMA2 represent the summatory function of sigma2, that is SIGMA2(n)=∑sigma2(i) for i=1 to n. The first 6 values of SIGMA2 are: 1,6,16,37,63 and 113. Find SIGMA2($10^{15}$) modulo $10^9$.

간략해석

1부터 $10^15$까지 자연수의 약수들의 제곱의 합의 합을 구하는 문제입니다. 답은 $10^9$로 나눈 나머지를 출력하면 됩니다.

Idea & Algorithm

naive idea

그냥 생각해보기

만약 각 수를 소인수 분해해서 문제를 푼다면, 약 시간복잡도는 $O\left(N\sqrt{N}\right)$정도 된다. 하지만 그렇게 풀면 평생해도 안풀린다.

생각바꾸기

1은 모든 수의 약수이다. 2는 모든 2의 배수의 약수이다. 3은 모든 3의 배수의 약수이다. … 그렇다면 n은 모든 n의 배수의 약수이다. 약수로 존재하는 1의 개수는 $\lfloor SZ \rfloor$, 2의 개수는 $\lfloor\frac{SZ}{2}\rfloor$ … 이므로 정답은 다음과 같은 방식으로 나타낼 수 있다.

\[ANS = \sum_{i==1}^{SZ} i^2 * \lfloor \frac{SZ}{i} \rfloor\]

하지만 이 방식을 그대로 진행한다면 시간복잡도는 $O(N)$이므로 하루 종일 돌리면 풀 수 있다. 아마도..?

advanced idea

$\left(\lfloor\frac{SZ}{2}\rfloor,SZ\right]$사이의 수를 살펴보면 이 수들은 각각 1번씩만 약수로써 나타난다.

그렇다면 이 생각의 연장선으로 수들을 횟수에 따라 그룹화 시킬 수 있다.

$\left(low, high\right)$의 횟수가 같다면 그 다음 그룹은 $low$로 시작한다는 것을 알 수 있다.

같은 횟수로 사용되는 수의 경우에는 다음과 같은 방식으로 합을 구할 수 있다.

\[f\left(N\right) = \sum_{i==1}^{N}i^2 = \frac{n\cdot(n+1)\cdot(2n+1)}{6}\] \[SUM(low,higt) = \lfloor\frac{SZ}{high}\rfloor * (f(high)-f(low))\]

이렇게 구하면 보다 빠르게 답을 구할 수 있다.

이 문제와 비슷하게 UCPC 2018 예선 문제가 있다.

source code

수 범위가 커서 overflow를 방지하기 위해 python을 이용해 풀었다. 그러나 왜 100초정도 시간이 소모되는지 모르겠다.

SZ = int(1e15)
MOD = int(1e9)

def sq_sum(n):
    return n*(n+1)*(2*n+1)//6

high = SZ
ANS = 0

while high != 0:
    cnt = SZ // high
    low = (SZ//(cnt+1))
    ANS += cnt * (sq_sum(high) - sq_sum(low))
    high = low

print (ANS % MOD)

Problem 401