UVa 11038 - How Many O's? | Sengxian's Blog

UVa 11038 - How Many O's?

#数学 #思维

Published on 2016-02-23

描述

将区间 $[a, b]$ 内的数写出来，一共有多少个 $0$ ？所有数均没有前缀 $0$ 且数 $0$ 含有 $1$ 个 $0$ 。所有数均在 $32$ 位无符号整数内。

样例输入

10 11
100 200
0 500
1234567890 2345678901
0 4294967295
-1 -1

样例输出

分析

本题求区间 $[a, b]$ 内 $0$ 的个数，不妨设 $f(n)$ 为区间 $[0, n]$ 内 $0$ 的个数，则答案为 $f(b) - f(a - 1)$ 。
如何计算 $f(n)$ 呢，对于一个数 $n$ 来说，我们考虑多少个数个位上有 $0$ ，多少个数十位上有 $0$ ，多少个数百位上有 $0$ ……依次，加起来就是答案。
考虑多少个数个位上有 $0$ 呢？例如 $353$ ，个位上有 $0$ 的只可能是 $10$ 、 $20$ 、 $30$ 、 $40$ 的形式，所以，有多少个 $10$ 就有多少个 $0$ 。 $353$ 个位上有 $0$ 的数有 $35$ 个！
多少个数百位上有 $0$ 呢？ $308$ ，百位上有 $0$ 的只可能是 $101$ 、 $201$ 、 $302$ 、 $409$ 的形式，所以，假设有 $x$ 个 $100$ 就一定有多少 $10(x-1)$ 个数百位上是 $0$ （对应 $10X$ 、 $20X$ ）。由于 $[300, 309]$ 不一定都能取到，所以我们讨论一下 $3$ 开头的情况， $[300, 302]$ 都是可行的。所以 $302$ 个位上有 $0$ 的有 $23$ 个！
多少个数千位上有 $0$ 呢？多少个数万位上有 $0$ 呢？多少个数十万位上有 $0$ 呢……
最后一定不要忘记 $+1$ ，别抛弃 $0$ 这家伙！

代码

//  Created by Sengxian on 2/23/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 11038 数学
#include <algorithm>
#include <iostream>
#include <cctype>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#define br putchar('\n');
using namespace std;

typedef long long ll;
inline ll ReadInt() {
    ll n = 0; int ch = getchar(); bool flag = false;
    while(!isdigit(ch)) flag |= ch == '-', ch = getchar();
    while(isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return flag ? -n : n;
}

ll power[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000LL};

ll f(ll x) {
    if(x < 0) return 0; //meaningless!
    if(x == 0) return 1;
    int digitNum = floor(log10(x)) + 1;
    ll ans = 0;
    for(int i = 1; i < digitNum; ++i) {
        ans += (x / power[i] - 1) * power[i - 1];
        if(x >= x / power[i] * power[i] + power[i - 1] - 1) ans += power[i - 1];
        else ans += x % power[i - 1] + 1;
    }
    return ans + 1; //Don't left 0!
}

int main() {
    ll a, b;
    while(a = ReadInt(), b = ReadInt(), ~a) {
        printf("%lld\n", f(b) - f(a - 1));
    }
    return 0;
}

附加输入

279704366 1037898461
145634828 978264788
146026069 848327284
2034117819 2145545070
1106351446 1941253829
1502186288 1640455732
1096870178 1262485963
1100447501 1763806630
61906328 1355138418
933991114 1164749943
0 4294967295
-1 -1

附加输出

UVa 10312 - Expression Bracketing UVa 10892 - LCM Cardinality