2025 Coding Team Tryouts P5 - Sphinxes and Math Team
Math Team has fallen into perilous danger and needs our help! A sphinx has taken over the premises, and refuses to give it back up until they answer its riddle:
You are given an integer \(N\) (\(1 \le N \le 10^6\)). For every ordered pair of integers \((a,b)\) (\(1 \le a,b \le N\)), calculate lcm\((a,b)\).
What is the sum of all such lcm\((a,b)\) mod \(10^9+7\)?
In other words, what is \(\sum_{a=1}^{N} \sum_{b=1}^{N} \mathrm{lcm}(a,b)\) (mod \(10^9+7\))?
With our hardy computers, we (Coding Team) shall save Math Team! You, heroic knight, can you solve the riddle?
Input Specification
The first and only line contains the integer \(N\).
For \(1/24\) of the subtasks, \(N \le 100\).
For \(4/24\) of the subtasks, \(N \le 1000\).
For \(24/24\) of the subtasks, \(N \le 10^6\).
Output Specification
Print one integer, the solution to the Sphinx's Riddle!
Sample Input
3Sample Output
28\((a,b)=(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\)
\(lcm(a,b)=1, 2, 3, 2, 2, 6, 3, 6, 3\)
\(\sum_{a=1}^{N} \sum_{b=1}^{N} \mathrm{lcm}(a,b)=28\) (mod \(10^9+7\))
Comments
I swear this is not optimal but I am very stupid. Please help me.