D. Fun with Integers

n이 주어졌을 때 2이상 n이하의 자연수를 가지고 주어진 연산을 했을 때 (a 를 b로 transform 할 때)

비율들의 절대값의 합의 최대치를 구하는 문제다.

n=4면

2 -> 4-> -2 -> -4 -> 2 이런식으로 2*4가 정답이고

n=6이면

2 -> 4 -> -2 -> -4 -> 2 -> 6 -> -2 -> -6 -> 3 -> 6 -> -3 -> -6 -> 2 이런식으로 2*4 + 2*4 + 3*4 = 28이 정답이다.

[2:n] 구간에서 (i,j) (ix = j && x는 2이상의 자연수) 를 모두 구하고 이때의 비율 x를 다 저장한 다음 *4 해주면 된다.

해법

dp 비슷하게 접근했다. 

d[n]을 function[2:n]의 결과값이라 하자.

d[n+1]은 d[n]에다가 [2:n] 구간에서 임의의 i를 뽑았을 때 i*x = n+1이 되는 모든 쌍을 구하고 그때의 x값을 더해준 값이 된다.

d[2] = 0

d[3] = 0

d[4] = 2

d[5] = 2   -> [2:4] 구간에서 5와 x배 되는 값이 하나도 없으므로 그대로 2

d[6] = 2 + 3 + 2  -> [2:5] 구간에서 (2,6), (3,6)이 정수배 관계에 있으므로 이 비율인 3,2를 더해준 값인 7

d[7] = 7

d[8] = 7 + (2,8) + (4,8) = 13

이런식으로 계산이 된다. 시간복잡도는 i가 n까지 돌아야 하므로 O(n), 그리고 i에 대해서 모든 약수를 구해야 하므로 O(sqrt(n))

합해서 O(n*sqrt(n))이 된다.

#include <iostream>
using namespace std;
 
typedef long long ll;
 
ll n;
ll d[100001];
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for (ll i = 4; i <= n; ++i) {
        d[i] = d[i - 1];
        for (ll j = 2; j*j <= i; ++j) {
            if (i%j == 0) {
                if (j*j == i) {
                    d[i] += i / j;
                }
                else {
                    d[i] += i / j;
                    d[i] += j;
                }
            }
        }
    }
    cout << d[n] * 4;
    return 0;
}