PROBLEM LINK:
Practice
Contest
Author and Editorialist: Soumik Sarkar
Tester: Avijit Agarwal
DIFFICULTY:
HARD
PREREQUISITES:
Mobius inversion
PROBLEM:
There is a grid with $N$ equally spaced horizontal lines and $M$ equally spaced vertical lines. What is the expected number of grid points on the perimeter of a randomly chosen non-degenerate triangle with vertices at grid points.
EXPLANATION:
The problem asks for the expected number of grid points on the perimeter of a randomly chosen triangle which has non-zero area. Let's call these $good$ triangles. As each good triangle is equally likely, the answer is equal to the sum of grid points on the perimeter of all good triangles divided by the number of good triangles.
$$ ans = \frac{good_{sum}}{good_{cnt}}$$
The number of grid points on the line segment joining $p_1=(x_1, y_1)$ and $p_2=(x_2, y_2)$ (including endpoints) minus one is given by $\gcd(|x_2-x_1|, |y_2 -y_1|)$. Let's denote this as $c(p_1, p_2)$ and assume we can get $c(p_1, p_2)$ for any pair of points in constant time.
Clearly the number of grid points on the perimeter of a triangle with vertices at $p_1$, $p_2$ and $p_3$ is given by $c(p_1, p_2) + c(p_2, p_3) + c(p_3, p_1)$.
We can iterate over all triplets of points $(p_1, p_2, p_3)$, and for each triplet increment $good_{sum}$ and $good_{cnt}$ appropriately if the triplet forms a good triangle. This approach has complexity $\mathcal{O}(n^3m^3)$.
Improvement 1
To calculate the sum and count of good triangles, we can instead subtract proper values of $bad$ triangles from that of $all$ triangles.
$$ ans = \frac{good_{sum}}{good_{cnt}} = \frac{all_{sum} - bad_{sum}}{all_{cnt} - bad_{cnt}} $$
View Content
Hide Content
Considering all possible triplets of points as vertices of triangles, we can say
$$\begin{aligned}
all_{sum} &= \sum_{p_1} \sum_{p_2} \sum_{p_3} (c(p_1, p_2) + c(p_2, p_3) + c(p_3, p_1)) \\
&= 3mn \sum_{p_1} \sum_{p_2} c(p_1, p_2) \\
all_{cnt} &= \sum_{p_1} \sum_{p_2} \sum_{p_3} 1 = n^3m^3
\end{aligned}$$
Note that some triangles are counted more than once here, and we will have to take care to remove the effect of the correct number of bad triangles.
All bad triangles have zero-area, but it will help to consider 3 cases of bad triangles separately. $badk$ triangles are triangles that have $k$ distinct vertices.
$$\begin{aligned}
bad1_{sum} &= 0 \\
bad1_{cnt} &= nm
\end{aligned}$$
For $bad1$, $p_1 = p_2 = p_3$. There are exactly $mn$ of these triangles, and there will be zero grid points on their perimeter, so we have the above results.
$$\begin{aligned}
bad2_{sum} &= 3 \sum_{p_1} \sum_{p_2} 2 c(p_1, p_2) \\
bad2_{cnt} &= 3 (n^2m^2 - nm)
\end{aligned}$$
In the above expression consider $p_1$as the point where 2 vertices coincide and $p_2$ as the 3rd vertex. The number of grid points on the perimeter of this triangle using our summation will equal $2c(p_1, p_2)$. In $bad2_{cnt}$ the $-nm$ term arises because $n^2m^2$ includes cases where $p_1=p_2$.
The terms above are multiplied by 3 because each such triangle was counted thrice in $all$ (when $p_1 = p_2 \ne p_3$ or $p_2 = p_3 \ne p_1$ or $p_1 = p_3 \ne p_2$) .
$$\begin{aligned}
bad3_{sum} &= 3 \sum_{p_1} \sum_{p_2} 2 c(p_1, p_2) (c(p_1, p_2) - 1)\\
bad3_{cnt} &= 3 \left(\sum_{p_1} \sum_{p_2} (c(p_1, p_2) - 1) + nm\right)
\end{aligned}$$
Consider a line $(p_1, p_2)$. Let the end points of this line be 2 vertices of a triangles. Then for every possible 3rd vertex on this line between $p_1$ and $p_2$ we have a bad triangle, and this number is $(c(p_1, p_2) - 1)$. However when $p_1 = p_2$ this value is $-1$ and to adjust that we have a $+nm$ term in $bad3_{cnt}$.
Each triangle under $bad3$ is counted 6 times in $all$ (as 3! permuations of $(p_1, p_2, p_3)$), and here we count each triangle twice (as 2! permuations of $(p_1, p_2)$) so again we multiply by 3 to make up the amount.
If we add them up as
$$\begin{aligned}
bad_{sum} &= bad1_{sum} + bad2_{sum} + bad3_{sum}\\
bad_{cnt} &= bad1_{cnt} + bad2_{cnt} + bad3_{cnt}\\
\end{aligned}$$
Then we have the answer as
$$ans = \frac{\displaystyle 3mn \sum_{p_1} \sum_{p_2} c(p_1, p_2) - 6 \sum_{p_1} \sum_{p_2} c(p_1, p_2)^2}{\displaystyle n^3m^3 - 3 \sum_{p_1} \sum_{p_2} c(p_1, p_2) - nm}$$
Now $\displaystyle\sum_{p_1} \sum_{p_2} c(p_1, p_2)$ and $\displaystyle\sum_{p_1} \sum_{p_2} c(p_1, p_2)^2$ can be calculated by iterating over all pairs of points, so we are down to $\mathcal{O}(n^2m^2)$.
Improvement 2
Let's expand $\displaystyle\sum_{p_1} \sum_{p_2} c(p_1, p_2)$ as $\displaystyle\sum_{x_1=1}^n \sum_{y_1=1}^m \sum_{x_2=1}^n \sum_{y_2=1}^m \gcd(|x_2-x_1|, |y_2 -y_1|)$.
Considering the unique values of $|x_2-x_1|=i$ and $|y_2-y_1|=j$, we can say
$$\begin{aligned}
\sum_{p_1} \sum_{p_2} c(p_1, p_2) &=nm\gcd(0,0) + 2m\sum_{i=1}^{n-1}(n-i)\gcd(i, 0) + 2n\sum_{j=1}^{m-1}(m-j)\gcd(0, j) \\
&+ 4\sum_{i=1}^{n-1} \sum_{j=1}^{m-1} (n-i) (m-j)\gcd(i, j)
\end{aligned}$$
A similar thing can be said for $\displaystyle\sum_{p_1} \sum_{p_2} c(p_1, p_2)^2$.
The first term in the expansion corresponds to cases of $p_1=p_2$ and can be calculated in constant time. The second and third terms deal with $p_1$ and $p_2$ on vertical and horizontal lines can be calculated in $\mathcal{O}(n + m)$, or even in constant time if one uses standard summation formulae. The last term requires $\mathcal{O}(nm)$.
Improvement 3
Here we focus on calculating $\displaystyle f_1(n, m) = \sum_{i=1}^n \sum_{j=1}^m (u-i) (v-j)\gcd(i, j)$ and $\displaystyle f_2(n, m) = \sum_{i=1}^n \sum_{j=1}^m (u-i) (v-j)\gcd(i, j)^2$.
Before proceeding further, I request you to go through this blog and this blog on multiplicative functions and Mobius inversion by Nisiyama_Suzune. I will be using identical notation as in the blog and the process used here is the same as described in the blog.
View Content
Hide Content
Assume without loss of generality $n \le m$, thus the gcd term never exceeds $n$.
$$\begin{aligned}
f_1(n, m) &= \sum_{i=1}^n \sum_{j=1}^m (uv - uj - vi + ij)\gcd(i, j) \\
&= \sum_{g=1}^n g \sum_{i=1}^n \sum_{j=1}^m (uv -uj-vi + ij)[\gcd(i, j) = g] \\
\end{aligned}$$
Substituting $i = ag$ and $j = bg$,
$$f_1(n, m) = \sum_{g=1}^n g \sum_{a=1}^{\lfloor n/g \rfloor} \sum_{b=1}^{\lfloor m/g \rfloor} (uv - ubg - vag + abg^2)[\gcd(a, b) = 1] $$
Applying Mobius inversion on $[\gcd(a, b) = 1]$,
$$\begin{aligned}
f_1(n, m) &= \sum_{g=1}^n g \sum_{a=1}^{\lfloor n/g \rfloor} \sum_{b=1}^{\lfloor m/g \rfloor} (uv - ubg - vag + abg^2) \sum_{d|\gcd(a,b)} \mu(d) \\
&= \sum_{g=1}^n g \sum_{a=1}^{\lfloor n/g \rfloor} \sum_{b=1}^{\lfloor m/g \rfloor} (uv - ubg - vag + abg^2) \sum_{d=1}^{\lfloor n/g \rfloor} [d|a][d|b] \mu(d) \\
&= \sum_{g=1}^n g \sum_{d=1}^{\lfloor n/g \rfloor} \mu(d) \left( uv \sum_{a=1}^{\lfloor n/g \rfloor} [d|a]\sum_{b=1}^{\lfloor m/g \rfloor} [d|b]- ug\sum_{a=1}^{\lfloor n/g \rfloor} [d|a]\sum_{b=1}^{\lfloor m/g \rfloor}[d|b]b - vg\sum_{a=1}^{\lfloor n/g \rfloor} [d|a]a\sum_{b=1}^{\lfloor m/g \rfloor}[d|b] + g^2\sum_{a=1}^{\lfloor n/g \rfloor}[d|a]a \sum_{b=1}^{\lfloor m/g \rfloor} [d|b]b \right) \\
\end{aligned}$$
Now $\sum_{i=1}^n [d|i] = \lfloor\frac{n}{d}\rfloor$ and $\sum_{i=1}^n [d|i]i = ds(\lfloor\frac{n}{d}\rfloor)$ where $s(n) = \frac{n(n+1)}{2}$.
$$f_1(n, m) = \sum_{g=1}^n g \sum_{d=1}^{\lfloor n/g \rfloor} \mu(d) \left(uv \lfloor \frac{n}{gd}\rfloor \lfloor \frac{m}{gd}\rfloor -ugd \lfloor \frac{n}{gd}\rfloor s(\lfloor \frac{m}{gd}\rfloor)-vgd\ s( \lfloor \frac{n}{gd}\rfloor) \lfloor \frac{m}{gd}\rfloor + g^2d^2s(\lfloor \frac{n}{gd}\rfloor)s(\lfloor \frac{m}{gd}\rfloor) \right)$$
Let $k = gd$, then,
$$f_1(n, m) = \sum_{k=1}^n \left(uv \lfloor \frac{n}{k}\rfloor \lfloor \frac{m}{k}\rfloor -uk \lfloor \frac{n}{k}\rfloor s(\lfloor \frac{m}{k}\rfloor)-vk\ s( \lfloor \frac{n}{k}\rfloor) \lfloor \frac{m}{k}\rfloor + k^2s(\lfloor \frac{n}{k}\rfloor)s(\lfloor \frac{m}{k}\rfloor) \right) \sum_{d|k}\mu(d) \frac{k}{d}$$
Similarly we can say,
$$f_2(n, m) = \sum_{k=1}^n \left(uv \lfloor \frac{n}{k}\rfloor \lfloor \frac{m}{k}\rfloor -uk \lfloor \frac{n}{k}\rfloor s(\lfloor \frac{m}{k}\rfloor)-vk\ s( \lfloor \frac{n}{k}\rfloor) \lfloor \frac{m}{k}\rfloor + k^2s(\lfloor \frac{n}{k}\rfloor)s(\lfloor \frac{m}{k}\rfloor) \right) \sum_{d|k}\mu(d) \frac{k^2}{d^2}$$
The function $\sum_{d|k}\mu(d) \frac{k}{d}$ is a multiplicative function which can be recognized as Euler's totient function $\varphi$. For a prime $p$, $\varphi(p^k) = p^k - p^{k-1}$.
$\sum_{d|k}\mu(d) \frac{k^2}{d^2}$ is another multiplicative function, let's denote it by $\varphi_2$. Clearly $\varphi_2(p^k) = p^{2k} - p^{2k-2}$.
Both functions can be computed using a linear sieve as described in the above mentioned blog post.
The complexity of the solution is now $\mathcal{O}(n + m)$ which fits in the given time limit.
AUTHOR'S AND TESTER'S SOLUTION:
Author's solution can be found here
Tester's solution can be found here.