Problem

floor[1*e] + floor[2*e] + floor[3*e] + … + floor[n*e],

where

`floor[x]`

is the largest integer that is not greater than x,

and e is Euler’s number: 2.7182818284..## Input

A single line which contains a single integer:

`n`

.## Output

A single line which contains a single integer which should be

the answer.## Constraints

1 ≤ n ≤ 10 ^ 4000

## Subtasks

Subtask #1 (50 points): 1 ≤ n ≤ 10 ^ 100

Subtask #2 (50 points): Original constraints.

## Example

## Input:

3

## Output:

15

## Explanation

`floor[1*e] = floor[2.71828..] = 2. floor[2*e] = floor[5.43656..] = 5. floor[3*e] = floor[8.15484..] = 8.`

So the answer is

`2+5+8=15`

.

**My Code**

```
Scanner in=new Scanner(System.in);
int T = in.nextInt();
double e=2.7182818284;
long sum=0;
for (int t_i = 1; t_i <= T; t_i++)
{
sum=Math.floor(sum+t_i*e);
// System.out.println(Math.floor(sum));
}
System.out.printf("%.0f",(sum));
```

This runs into a time-limit exceeded.

Solution

`int`

, `long`

and `double`

are not precise enough. You should probably use `BigInteger`

and/or `BigDecimal`

instead.

Same problem with `e=2.7182818284;`

. When you do `100000000000L*e`

you’re already off by almost 6. And this is nothing compared to 10100${10}^{100}$.

Even if you use `Math.E`

instead it’s only `2.718281828459045`

. So you probably want to calculate `e`

to an arbitrary precision (based on input `n`

) instead. (Check here for a hint).

Note that none of those will help you with the time-limit-exceeded problem though. You’ll have to find a smarter way so that you don’t have to iterate all 104000${10}^{4000}$ numbers. Note that if you would add a number each millisecond and you ran the program for 300 years you would still only reach about 1012${10}^{12}$ or 1013${10}^{13}$. So no where close to what you want.

The best I can come up with is to keep track of the actual sum, the floored sum and the error on each order of magnitude.

So for n = 10, then n=100, then n=1000, …

At each step you use the result of the previous one. That way you only need to do 10 iterations in the loop at that step to go up an order of magnitude.

Once you have those results you can calculate for any `n`

the wanted result. The tricky part here is how to correct the error’s at each step.

Even for n=104000$n={10}^{4000}$ this should only result in O(10000) operations which (depending on your machine specs) runs in less than a minute. (Might also depend on how long calculations with `BigInteger`

/`BigDecimal`

take, I don’t have much experience with those myself).

How to actually implement this I’ll leave up to you, since this site is all about improving existing code, not just writing new code to solve the problem for you 🙂

**Disclaimer**: I did not test this myself yet, so not 100% sure that it will be fast enough even if implemented correctly.