PROBLEM LINK:
Author: Full name
Tester: Full name
Editorialist: Oleksandr Kulkov
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
None
PROBLEM:
You have to calculate \sum\limits_{k=1}^n \lfloor k\cdot e\rfloor with n \leq 10^{4000}.
QUICK EXPLANATION:
See the pictures below for n=6.
EXPLANATION:
Geometrically, we have to count lattice points with 0 < y \leq ex. Let’s add to the answer points below y=\lfloor e\rfloor x = 2x. There are \lfloor e \rfloor \cdot \dfrac{n(n+1)}{2}=n(n+1) of them. Now there is one to one correspondence between remaining points and points below y=(e-\lfloor e \rfloor)x. Let’s transform plane in such a way that (n, \lfloor(e-\lfloor e \rfloor)n\rfloor) point will move to (0,0). Now we have to count lattice points below y=\dfrac{x+(e-\lfloor e \rfloor)n-\lfloor(e-\lfloor e \rfloor)n\rfloor}{e-\lfloor e \rfloor}, thus we returned to the task of counting points below y=kx+b with k>1. Let’s see how it works for n=6 and proceed to the formal algorithm.
Now assume we want to count lattice (x;y) such that 0 \le x < n and 0 < y \le kx+b. Which is \sum\limits_{x=0}^{n-1}\lfloor kx+b \rfloor.
- If k>1 or b>1, we can count points with y\le\lfloor k\rfloor x + \lfloor b\rfloor which is \sum\limits_{t=0}^{n-1} \lfloor k \rfloor t + \lfloor b \rfloor=\dfrac{(\lfloor k\rfloor (n-1) + 2 \lfloor b \rfloor)n}{2}. Now we have to count points in \lfloor k \rfloor x + \lfloor b \rfloor < y\leq kx+b which is same as counting points in 0< y\leq (k-\lfloor k \rfloor)x+(b-\lfloor b \rfloor). Thus k'=k-\lfloor k \rfloor < 1, b' = b-\lfloor b \rfloor < 1.
- If k < 1 and b < 1 then considering that there are no lattice points in x< 0, 0< y\le kx+b because b < 1 and in x< n, \lfloor k n + b \rfloor < y\le kx+b, we can rotate the trapezium in such way that new origin is situated in (n;\lfloor k n + b \rfloor), y-axis moves to the left and x-axis moves to the bottom, as you may see on the picture:
One can see that now we deal with 0\leq x < \lfloor kn+b\rfloor and 0< y\le \dfrac{x+(kn+b)-\lfloor kn+b\rfloor}{k} which refers us to the case 1 since k'>1.
Let’s do some complexity analysis now. We assume b to be negligible compared to kn since we can get b< 1 at the first step of case 1. In that case there are at most \dfrac{kn(n-1)}{2} points we have to count and we getting rid of \dfrac{\lfloor k \rfloor n(n-1)}{2} of them. So part of removed points is at least \dfrac{\lfloor k \rfloor}{k}\geq \dfrac 1 2. Thus this solution works in O(\log n) steps. You have to calculate euler’s number with high precision in this problem which is possible using continued fractions or series e=\sum\limits_{n=0}^\infty\dfrac{1}{n!}. Please observe the details in the following link.
Another solution based on Beatty theorem can be found here. And another one solution is based on this article.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.