UVA 11038 - How Many O's? 计算对答案的贡献

时间：2023-03-08 20:08:43
题意：   求[n, m]之间包含0的数字的个数
题解：转化为求solve(n) - solve(m-1)的前缀问题
　　　　对于求0到n的解，我们举例 n = 25789 对于8这位，让其为0对答案的贡献是  （0~257）*（0~9）
　　　　　假设是 n = 25709  那么让这位为0的答案贡献是 （0~256） * （0~9） + （257）* （0~9）


//meek///#include<bits/stdc++.h>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include<iostream>

using namespace std ;

#define mem(a) memset(a,0,sizeof(a))

#define pb push_back

#define fi first

#define se second

#define MP make_pair

typedef long long ll;

const int N = (<<)*;

const int M = ;

const int inf = 0x3f3f3f3f;

const int MOD = ;

const double eps = 0.000001;

ll n,m;

ll solve(ll l) {

    if(l <  ) return ;

    ll x = , r = ;

    ll ans = ;

    while(l >= ) {

        ll now = l % ;

        l /= ;

        if(now) ans += l*x;

        else ans += (l-)*x + r + ;

        r = r + now*x;

        x *= ;

    }

    return ans;

}

int main() {

    while(scanf("%lld%lld",&n,&m)!=EOF) {

        if(n == - && m == -) break;

        printf("%lld\n", solve(m) - solve(n-));

    }

    return ;

}