I sometimes make problems and post them in Japanese local contest yukicoder. I want many people to know math problems I made, so I introduce some of them. Let's try!!
LCMST
Problem Statement
Consider a complete graph $$$G$$$ on $$$N$$$ vertices. The weight of edge between vertex $$$i$$$ and $$$j$$$ is least common multiple of $$$A_i$$$ and $$$A_j$$$. Find the total weight of the edges contained in a minimum spanning tree of $$$G$$$.
Constraints
- $$$2\leq N \leq 10^6$$$
- $$$1\leq A_i\leq 10^5$$$
- Time Limit is 4000ms
Sample
When $$$N=3$$$ and $$$A=(2,3,4)$$$, the answer is 10. This is optimal to draw edges between $$$(1,2),(1,3)$$$. These have weights $$$\mathrm{lcm}(A_1,A_2)=\mathrm{lcm}(2,3)=6, \mathrm{lcm}(A_1,A_3)=\mathrm{lcm}(2,4)=4$$$, respectively.
Hints
Simple Math ?
Problem Statement
You are given integer $$$a$$$ and $$$N$$$. Find $$$\displaystyle \sum_{i=1}^N \lfloor \sqrt{ai}\rfloor\ \mathrm{mod}\ 10^9+7$$$. You have $$$T$$$ test cases to solve.
Constraints
- $$$1\leq T \leq 10$$$
- $$$1\leq a \leq 10^6$$$
- $$$1\leq N\leq 10^{12}$$$
- Time Limit is 2000ms
Sample
When $$$a=2$$$ and $$$N=5$$$, the answer is $$$\lfloor \sqrt{2} \rfloor+\lfloor \sqrt{4} \rfloor+\lfloor \sqrt{6} \rfloor+\lfloor \sqrt{8} \rfloor+\lfloor \sqrt{10} \rfloor=1+2+2+2+3=10$$$.
