C - ABC conjecture Editorial by en_translator


Consider a brute force search in which the values of \(A\), \(B\) and \(C\) are decided in this order. Since \(A\leq B \leq C\), \(A\) should be in the range of \(1\leq A\leq \sqrt[3]{N}\). Similarly, once \(A\) is fixed, \(B\) should be in the range of \(A\leq B \leq \sqrt{\frac{N}{A}}\); once \(A\) and \(B\) are fixed, \(C\) should be in the range of \(B \leq C \leq \frac{N}{AB}\).

The following pseudocode is a naive implementation of this procedures, which counts all triplets that satisfies the conditions.

Pseudocode 1 (TLE)

ans=0
for A=1 to pow(N,1/3)
	for B=A to pow(N/A,1/2)
		for C=B to N/(A*B)
			ans+=1
print(ans)

In this pseudocode, evidently the innermost loop on \(C\) is repeated \(\left\lfloor\frac{N}{AB}\right\rfloor-B+1\) times. So one can rewrite the code as follows.

Pseudocode 2

ans=0
for A=1 to pow(N,1/3)
	for B=A to pow(N/A,1/2)
		ans+=floor(N/(A*B))-B+1
print(ans)

In fact, this pseudocode operates in a total of \(O(N^{2/3})\) time, which is fast enough to obtain AC.

When implementing, be careful of the computational errors.

Sample code (C)
Sample code (Python)

We will now explain why the complexity is \(O(N^{2/3})\).

Under certain assumptions, the order of the complexity of Pseudocode 2 corresponds to how many times the fourth line is executed; that is, to the number of loops. Also, the number of loops is obviously \(\displaystyle \sum _{A=1}^{\sqrt[3]{N}} \left(\sqrt{\frac{N}{A}}-A+1 \right)\).
Regarding the expression after the sigma as a function of \(A\), it is a monotonically decreasing function, so
\(\displaystyle \sum _{A=2}^{\sqrt[3]{N}} \left(\sqrt{\frac{N}{A}}-A+1 \right) \leq \int_{1}^{\sqrt[3]{N}}\left(\sqrt{\frac{N}{A}}-A+1 \right)dA.\)
(Note that the lower bound of \(A\) in the left hand side is \(2\).)
(The derivation is similar to when estimating the order of the harmonic series. Verify it by visualizing it)

The integral in the left hand side turns out to be \(O(N^{2/3})\). Therefore \(\displaystyle \sum _{A=1}^{\sqrt[3]{N}} \left(\sqrt{\frac{N}{A}}-A+1 \right) \leq \left(\sqrt{\frac{N}{1}}-1+1 \right)+O(N^{2/3})=O(N^{2/3}),\)
thus the claim has been proven.

posted:
last update: