Contest Duration: - (local time) (100 minutes) Back to Home

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.

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: