ABC339 F - Product Equality
Competitive Programming C++
2024-02-07
공식 에디토리얼
문제 링크
https://atcoder.jp/contests/abc339/tasks/abc339_f
원문 링크
https://atcoder.jp/contests/abc339/editorial/9206
\(2\)개의 변수를 골라 곱하는 방법은 \(N^2\)가지 있습니다.
하지만 각 변수는 매우 크기 떄문에, 단순하게 구하려고 하면(오버플로우를 고려하지 않고) 큰 수 연산을 사용한다고 해도 자릿수를 \(d\)라 할 때 \(O(N^2 d \log d)\)정도의 계산량이 되는 걸 예상할 수 있으며, 이 방법으로는 정답을 맞추기 어렵습니다.
일단 어떤 \(3\)개의 변수 \(p, q, r\)에 대해 \(p \times q = r\)이 되는지 판정해봅시다.
여기서 아래처럼 조금 대담하게 판정을 해 볼 수도 있습니다.
- 어떤 정수 \(x\)를 선택해, \(p \times q \equiv r(\mathrm{mod} x)\)라면 \(p \times q = r\)이라고 판정한다.
이 방법은 \((p \times q - r) \equiv 0(\mathrm{mod} x)\)일 땐 실패합니다.
여기서 \(x\)로 \(10^9\) 이상의 소수를 선택하는 것을 생각할 수 있습니다.
이 떄, 이 판정이 실패하는 \(x\)는 많아야 \(222\)개 밖에 없습니다.(\(\vert p \times q - r \vert \leq 10^{2000}\)이므로) 여기서 \(10^9\) 이상 \(2 \times 10^9\)이하 소수는 수천만 개 있습니다.
그렇기 때문에, 사실 이하의 무작위화 알고리즘이 정답이 됩니다.
- \(S =\)임의로 선택한 원소들의 집합(각 원소는 \(10^9\)이상 \(2 \times 10^9\)이하의 소수) 이라고 한다.
- \(S\)에 속한 모든 원소 \(x\)에 대해 \(A_i \times A_j \equiv A_k(\mathrm{mod} x)\)가 성립한다면 \(A_i \times A_j = A_k\) 라고 판정한다.
- 미리 모든 \(A_k\)에 대해 \(S\)에 속한 각각의 원소 \(x\)로 \(\mathrm{mod}\)를 취한 값을 전처리해두고, 거기에 \(A_i \times A_j\)에 \(\mathrm{mod}\)를 취한 값이 일치하는지 판정한다.
이것으로 \(O(\vert S \vert \times N^2 \log N)\)에 이 문제의 정답을 구할 수 있습니다. 성공 확률을 정밀히 계산하는 것은 생략하겠습니다만, \(\vert S \vert\)로 \(20\)개 정도 적당한 조건에 맞는 소수를 선택하면 될 것입니다.
또한, \(x\)에 대해 소수 판정을 하지 않고, 그냥 적당히 큰 정수를 선택하는 것만으로도 이 문제의 답을 맞출 수도 있습니다.(이런 방법을 모두 저격(틀리게 만드는 테스트 케이스를 준비)하기란 매우 어렵습니다.)
다른 에디토리얼
원문 링크
https://atcoder.jp/contests/abc339/editorial/9220
큰 정수의 사칙연산은 자릿수가 클 수록 계산에 시간이 걸립니다.
따라서, 자릿수가 큰 사칙연산을 하는 횟수를 줄이면 되는 것 아니냐 생각할 수 있습니다.
이 문제를 무식하게 푸는 방법을 생각해봅시다.
\(i, j\)를 완전 탐색하여 곱이 \(A_k\)와 일치하는 \(k\)의 개수의 합을 구한다
이런 접근으로 C++에서 boost의 큰 수 라이브러리를 이용해 풀 수 있습니다.
\(A\)가 정렬되어 있고, \((i, j)\)의 쌍이 \(A_i \times A_j > A_N\)을 만족한다고 합시다. 이 때, \(j < l\)을 만족하는 \(l\)에 대해서는 \((i, l)\)에 대해 탐색하지 않아도 됩니다.
이 정도 구현으로 이번 테스트 케이스들에 대해서는 정답을 받을 수 있습니다.
랜덤이 나이브로 뚫려?
무작위화로 저렇게 하는게 정해라는 것도 놀랍긴 한데,
이걸 그냥 라이브러리를 동원한 나이브한 풀이로 뚫는게 있었다.
무서운 CP의 세계.