[Codeforces] Round 813 LCMSum

문제링크 : LCMSum (hardversion)

문제

$LCM(i, j, k) >= i + j + k$을 만족하는 $(i, j, k)$의 쌍의 수를 구하여라
(단, $l < i < j < k < r$)

문제 접근

$LCM(i, j, k) >= i + j + k$ 인 경우의 수를 구하게 되면, $O(n^3)$의 시간이 걸린다.
따라서 전체 경우의 수 - 조건을 만족하지 않는 경우의 수를 이용하여 풀어야 한다.

---

전체 경우의 수

전체 경우의 수 $= \binom{r-l+1}3$

l, r 사이에서 숫자를 3개 뽑는 것이므로 위의 같이 구하면 된다.

조건을 만족하지 않는 경우의 수

$i$와 $j$의 값이 $nk$의 약수일 경우, $LCM(i, j, k) = nk$ 가 되기 때문에
$nk$의 값만 생각해주면 된다.

1) $LCM(i, j, k) = k$

$0 >= i + j$ 는 성립하지 않기 때문에 이 경우에는 문제의 조건을 무조건 만족하지 않는다.

2) $LCM(i, j, k) = 2k$

$k < i + j$ 인 경우에 한하여 문제의 조건을 만족하지 않는다.

3) $LCM(i, j, k) = 3k$ 이상

$2k \ge i + j$ 를 만족하는 "$k$ 보다 작으며, $3k$의 약수인 $i, j$" 는 존재하지 않음.

---

위의 3가지 경우를 보면,
$i, j$가 $2k$의 약수일 때, 문제의 조건이 성립되지 않는다는 것을 알 수 있다.

코드

#include <iostream>
#include <vector>
#define MAX 400005

using namespace std;
using lld = long long;

struct Query {
	int left;
	int i;
};

vector<lld> ans(MAX);
vector<vector<Query>> queries(MAX, vector<Query>());


// 펜윅트리
vector<int> fenwick(MAX);
void add(int k) {
	while (k < MAX) {
		fenwick[k] += 1;
		k += k & -k;
	}
}
int sum(int k) {
	int s = 0;
	while (k > 0) {
		s += fenwick[k];
		k -= k & -k;
	}
	return s;
}

// i와 j는 2k의 약수이기 때문에, lcm(lcm(i, j), k)
int lcm(int i, int j, int k) {
	if (k % i == 0 && k % j == 0) {
		return k;
	}
	return 2 * k;
}

// 전체 경우의 수 구하기
lld combi(lld len) {
	return len * (len - 1) * (len - 2) / 6;
}

int main() {
	// k의 약수 구하기
	vector<vector<int>> divisor(MAX * 2 + 1);
	for (int i = 1; i < MAX; i++) {
		for (int j = i + i; j < MAX; j += i) {
			divisor[j].push_back(i);
		}
	}

	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		int l, r;
		cin >> l >> r;
		queries[r].push_back({ l, i });
	}

	int total = 0;
	for (int k = 1; k <= 200000; k++) {
		for (auto j : divisor[k * 2]) {
			// j가 k보다 같거나 커지면, 3개 이상을 고를 수 없음.
			if (j >= k) {
				break;
			}

			for (auto i : divisor[k * 2]) {
				// i가 j보다 커지면, 전제조건(i < j < k)에 모순
				if (i >= j) {
					break;
				}

				// k < i + j 확인
				int L = lcm(i, j, k);
				if (L < i + j + k) {
					total++;
					add(i);
				}
			}
		}

		// 현재 k가 input으로 주어진 값이라면, 
		// total - sum(cur.left - 1) 한 값을 전체의 경우(=combi)에서 뺴줌
		// i는 l보다 커야 되기 때문에 total에서 sum(cur.left - 1) 한 값을 뺴주는 것.
		for (Query& cur : queries[k]) {
			ans[cur.i] = combi(k - cur.left + 1) - (total - sum(cur.left - 1));
		}
	}

	// 전체 경우에서 안되는 경우를 뺌
	for (int i = 0; i < t; i++) {
		cout << ans[i] << "\n";
	}

	return 0;
}

설명

테스트 케이스는 총 10^5이고, r의 최대값은 2*10^5 이므로,
입력이 들어올 때마다 계산을 처리하면 시간초과가 발생할 것이다.
따라서 해당 문제를 빠르게 구하기 위해 offline query를 이용한다.

1. queries 배열의 인덱스를 $r$로 하고, 값을 { $l, idx$ }로 세팅함으로써 offline query로 처리할 수 있도록 한다.
2. k를 1부터 200000 까지 돌면서 안되는 경우를 total에 더해준다.
   • 만약, k에 대한 query가 존재할 경우, $total - (query[k].left - 1)$로 $l$ ~ $r$ 사이에 안되는 경우를 구해준다.
   • 그리고 $l$ ~ $r$ 사이에서 전체 경우는 $\binom{r-l+1}3$ 이다.
   • 주의) 구간에 대한 연산이 많이 필요하므로 펜윅 트리를 이용하여 $O(log$ $n)$ 시간에 구할 수 있도록 해야한다.
3. 2번에서 구한 정답을 ans 배열에다가 따로 저장해둔 뒤, k에 대한 모든 연산이 끝난 후 한번에 출력해준다.