409406: GYM103500 E Factors

Let $$$f(\prod p_i^{a_i})=\sum a_ip_i$$$, where $$$p_i$$$ are primes. In particular, $$$f(1)=0$$$.

Define $$$g(n,k,r)$$$ to be the sum of all $$$i^k$$$ where $$$i$$$ is a positive integer less than $$$n$$$ and $$$f(i)\equiv r\pmod 4$$$.

Given $$$m$$$ and $$$k\in\{0,1\}$$$, for all integers $$$i$$$ where $$$1\le i\le \lfloor\sqrt m\rfloor$$$, find $$$g(\lfloor\frac{m}{i}\rfloor,k,0\dots 3)$$$.

The first line contains two integers $$$m$$$ and $$$k$$$ ($$$1\le m\le 10^{10}$$$, $$$0\le k\le 1$$$).

Output $$$\lfloor\sqrt m\rfloor$$$ lines. The $$$i$$$-th of these lines should contain four integers, corresponding to $$$g(\lfloor\frac{m}{i}\rfloor,k,0)$$$, $$$g(\lfloor\frac{m}{i}\rfloor,k,1)$$$, $$$g(\lfloor\frac{m}{i}\rfloor,k,2)$$$, and $$$g(\lfloor\frac{m}{i}\rfloor,k,3)$$$, respectively.

• In the first subtask, worth $$$5$$$ points, $$$m\le 10^7$$$.
• In the second subtask, worth $$$15$$$ points, $$$n\le 10^9$$$ and $$$k=0$$$.
• In the third subtask, worth $$$25$$$ points, $$$k=0$$$.
• In the fourth subtask, worth $$$25$$$ points, $$$n\le 10^9$$$.
• In the final subtask, worth $$$30$$$ points, no additional constraints are posed.

10 0

2 2 3 3
2 1 1 1
1 0 1 1

10 1

5 11 19 20
5 5 2 3
1 0 2 3