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; } | cs |
'codeforces > #520 div2' 카테고리의 다른 글
| C. Banh-mi (0) | 2018.11.17 |
|---|---|
| B. Math (0) | 2018.11.17 |
| A. A Prank (0) | 2018.11.17 |