PROBLEM LINK:
Author: Madhav Sainanee
Tester: Prakhar Gupta
Editorialist: Prakhar Gupta
DIFFICULTY:
SIMPLE
PREREQUISITES:
Arithmetic Progression, Sum of internal angles of a polygon, Arithmetic of fractions.
PROBLEM:
Given an n sided polygon with the first angle a, find out the k^{th} angle if all the angles are in Arithmetic Progression with the first angle being the smallest.
QUICK EXPLANATION
Find out the sum of AP from the sum of internal angles of the polygon. The common difference can be calculated from the sum of AP and can be used to find the k^{th} angle.
EXPLANATION:
The sum of internal angles of an n sided polygon, S = 180 \times (n - 2).
This also forms the sum of the AP, i.e. S = \frac {n}{2} (2a + (n - 1) d).
From the above equation, we can find out d as a fraction.
The K^{th} angle can then be can be found out as A_k = a + (k - 1) d.
Since the numerator and denominator A_k may not be co-prime by now, divide both of them by their gcd.
Complexity: The time complexity is O(1 + log(n^2)) per test case, due to the gcd.
Note: We also allowed naive O(N) gcd algorithm.
AUTHOR’S SOLUTION:
Author’s solution can be found here.