题目描述

一本书的页码是从1—n编号的连续整数：1,2,3,…,n。请你求出全部页码中所有单个数字的和，例如第123页，它的和就是1+2+3=6。

输入格式：

一行为n(1≤n≤1O^9)。

输出格式：

一行，代表所有单个数字的和。

输入样例#1：

3456789

输出样例#1：

96342015

题解：

10^9的数据，暴力跑肯定是没戏的，但我们可以采取分块打表的思想。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
int main()
{
    int n, now = 0;
    cin >> n;
    ll ans = 0, sum = 0;
    for (int i = 0; i <= 9999; i++)
    {
        int t = i;
        for (int j = 0; j < 4; j++)
            sum += t % 10, t /= 10;
    }
    for (int i = 1; i <= 9999; i++)
    {
        int t = i;
        while (t != 0)
            ans += (t % 10), t /= 10;
        if (i == n)
        {
            printf("%lld\n", ans);
            return 0;
        }
    }
    for (int i = 9999; i + 10000 <= n; i += 10000)
    {
        int p = 0, t = (i + 1) / 10000;
        while (t != 0)
            p += t % 10, t /= 10;
        ans += p * 10000 + sum;
        now = i;
    }
    now += 10000;
    for (int i = now + 1; i <= n; i++)
    {
        int t = i;
        while (t != 0)
            ans += (t % 10), t /= 10;
    }
    printf("%lld\n", ans);
    return 0;
}