1344. Add Up What Is Coprime To It
Print the sum of every integer from 1 to n that shares no factor with n
beyond 1.
10 -> 1 + 3 + 7 + 9 = 20
12 -> 1 + 5 + 7 + 11 = 24
Testing each value with a gcd is O(n log n), far too slow at n = 10^12.
Problem 1319 counts these numbers. This one adds them, and the step from one to the other is a symmetry worth seeing rather than a new algorithm.
If x is coprime to n, so is n - x, because any common factor of n - x and
n would divide their sum x as well. So for n > 1 the coprime numbers pair
up as x and n - x, every pair sums to n, and there are half as many pairs as
numbers:
sum = n * totient(n) / 2
which reuses problem 1319 exactly and costs nothing more.
n = 1 breaks the pairing, because 1 is coprime to itself and pairs with
n - 1 = 0, which is not in range. The formula gives 0 and the true answer is 1,
so that case is handled on its own.
The product reaches 10^12 times 10^12, so reduce by dividing the even factor
before multiplying: totient(n) is even for every n > 2.
Constraints - `1 ≤ n ≤ 1000000`
Input
One line containing the integer n.
Output
Print the sum of the integers from 1 to n that are coprime to n.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.