AtCoder—E - Σ[k=0..10^100]floor(X／10^k

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 500500 points

Problem Statement

Find \displaystyle \sum_{k=0}^{10^{100}} \left \lfloor \frac{X}{10^k} \right \rfloork=0∑10100​⌊10kX​⌋.

Notes

\lfloor A \rfloor⌊A⌋ denotes the value of AA truncated to an integer.

Constraints

• XX is an integer.
• 1 \le X < 10^{500000}1≤X<10500000

---

Input

Input is given from Standard Input in the following format:

XX

Output

Print the answer as an integer.
Here, the answer must be precisely printed as an integer, even if it is large. It is not allowed to use exponential notation, such as 2.33e+21, or print unnecessary leading zeros, as in 0523.

---

Sample Input 1 Copy

Copy

1225

Sample Output 1 Copy

Copy

1360

The value we seek is 1225+122+12+1+0+0+\dots+0=13601225+122+12+1+0+0+⋯+0=1360.

---

Sample Input 2 Copy

Copy

99999

Sample Output 2 Copy

Copy

111105

Beware of carries.

---

Sample Input 3 Copy

Copy

314159265358979323846264338327950288419716939937510

Sample Output 3 Copy

Copy

349065850398865915384738153697722542688574377708317

The values in input and output can both be enormous.

 解题思路：估计你看到下面这张图图之后就恍然大悟了。

 这里我们很容易看到两个绿圈的规律。

Code:

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

const int N = 100010;

typedef long long LL;

int n, m, sum, cnt;
string s, t;

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> s;
	for(int i = 0; i < s.size(); i ++ )  sum += s[i] - '0'; //绿圈求和
	for(int i = s.size() - 1; i >= 0; i -- )
	{
		cnt += sum; //每次循环后的绿圈求和
		t.push_back((cnt % 10) + '0');
		cnt /= 10;
		sum -= s[i] - '0';
	}
	if(cnt)  t.push_back(cnt + '0');
	reverse(t.begin(), t.end());
	cout << t << endl;
}