Luogu-P2567-幸运数字

Posted on 2024-10-04 Edited on 2025-02-24 Word count in article: 562

题目 P2567 [SCOI2010] 幸运数字

题目背景

四川 NOI 省选 2010。

题目描述

在中国，很多人都把 $6$ 和 $8$ 视为是幸运数字！lxhgww 也这样认为，于是他定义自己的“幸运号码”是十进制表示中只包含数字 $6$ 和 $8$ 的那些号码，比如 $68$ ， $666$ ， $888$ 都是“幸运号码”！但是这种“幸运号码”总是太少了，比如在 $[1,100]$ 的区间内就只有 $6$ 个（ $6$ ， $8$ ， $66$ ， $68$ ， $86$ ， $88$ ），于是他又定义了一种“近似幸运号码”。lxhgww 规定，凡是“幸运号码”的倍数都是“近似幸运号码”，当然，任何的“幸运号码”也都是“近似幸运号码”，比如 $12$ ， $16$ ， $666$ 都是“近似幸运号码”。

现在 lxhgww 想知道在一段闭区间 $[a, b]$ 内，“近似幸运号码”的个数。

输入格式

输入数据是一行，包括 $2$ 个数字 $a$ 和 $b$ 。

输出格式

输出数据是一行，包括 $1$ 个数字，表示在闭区间 $[a, b]$ 内“近似幸运号码”的个数。

思路：打表

快乐打表~

不难发现，本题的幸运数字数量很少。

于是考虑打表的可能性。

但是一个一个存储显然会MLE，考虑区间打表。

区间打表（也叫分块打表）就是已知每段区间上的答案，最终只要求出超出区间部分的即可。

例如：每段区间的长度为 $5$ ，已知 $1 \sim 5$ 和 $6 \sim 10$ 上的答案，想求出 $1 \sim 7$ 上的答案，只需要查表获取 $1 \sim 5$ 上的答案，再计算出 $6 \sim 7$ 上的答案即可。

打表过程

第一步：获取数据

先打表获取所有的幸运数字。

// template v9
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int inf = 0x7f7f7f7f;

void bfs(){
    queue<ll> q;
    q.push(0);
    while(q.size()){
        ll x = q.front();
        q.pop();
        cout << x << ',';
        if(x * 10 < 1e10){
            q.push(x * 10 + 6);
            q.push(x * 10 + 8);
        }
    }
}

int main() {
    freopen("step1.out", "w", stdout);
    cout << '{';
    bfs();
    cout << '}';
    return 0;
}

第二步：分割区间

由于本题的数据范围是 $1 \sim 10^{10}$ ，所以考虑一个合适的区间长度： $10^7$ 。

于是，可以写出第二段程序，计算出每段区间内的近似幸运数字。

// template v8
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int inf = 0x7f7f7f7f;

ll arr[] = {}; // step1.out

const ll len = 1e7;

bool b[len + 10];

const int L = sizeof arr / sizeof (ll);
// [l, r]
int query(ll l, ll r){
    memset(b, 0, sizeof b);
    ll ans = 0;
    for(ll i = 0; i < L; i++){
        for(ll j = r / arr[i] * arr[i]; j >= l; j -= arr[i]){
            b[j - l] = true;
        }
    }
    for(ll i = l; i <= r; i++){
        ans += b[i - l];
    }
    return ans;
}

int main() {
    freopen("step2.out", "w", stdout);
    cout << '{';
    for(ll i = 0; i < (ll)1e10; i += len){
        ll ans = query(i + 1, i + len);
        cout << ans << ',';
        cout.flush();
    }
    cout << '}';
    return 0;
}

由于长度限制，此处不提供具体数据。

第三步：最终程序

这里要做的就是最终要提交的程序了。

利用分块打表，就能做到最多计算 $10^7$ 长度的区间了。

// template v9
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int inf = 0x7f7f7f7f;

ll arr[] = {}; // step1.out

const ll len = 1e7;

bool b[len + 10];

const int L = sizeof arr / sizeof (ll);

int t[] = {}; // step2.out

ll query(ll l, ll r){
    memset(b, 0, sizeof b);
    ll ans = 0;
    for(ll i = 0; i < L; i++){
        for(ll j = r / arr[i] * arr[i]; j >= l; j -= arr[i]){
            b[j - l] = true;
        }
    }
    for(ll i = l; i <= r; i++){
        ans += b[i - l];
    }
    return ans;
}

ll query(ll x){
    ll ans = 0, i = 0;
    for(; i * len <= x - len; i++){
        ans += t[i];
    }
    return ans + query(i * len, x);
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    ll l, r;
    cin >> l >> r;
    cout << query(r) - query(l - 1) << endl;
    return 0;
}

AC Code

// template v9
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int inf = 0x7f7f7f7f;

ll arr[] = {}; // step1.out

const ll len = 1e7;

bool b[len + 10];

const int L = sizeof arr / sizeof (ll);

int t[] = {}; //

ll query(ll l, ll r){
    memset(b, 0, sizeof b);
    ll ans = 0;
    for(ll i = 0; i < L; i++){
        for(ll j = r / arr[i] * arr[i]; j >= l; j -= arr[i]){
            b[j - l] = true;
        }
    }
    for(ll i = l; i <= r; i++){
        ans += b[i - l];
    }
    return ans;
}

ll query(ll x){
    ll ans = 0, i = 0;
    for(; i * len <= x - len; i++){
        ans += t[i];
    }
    return ans + query(i * len, x);
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    ll l, r;
    cin >> l >> r;
    cout << query(r) - query(l - 1) << endl;
    return 0;
}