目录

• 一、 题目描述
• 1. 输入
• 2. 输出
• 3. Limits
• 二、 解题思路
• 1. 对于第一个条件的解决
• 2. 对于第二个条件的解决
• 2. 1 两个区间的划分
• 2. 2 对整组部分的处理
• 2. 3 对非整组部分的处理
• 三、 代码描述

一、 题目描述

  查数游戏，参与者不能说出被9整除或数位中含有9的数字。

1. 输入

  T：表示共有T个用例来进行测试
  F，L：表示查数的区间 [F, L]
  注：F和L都是可以被喊出的数字（即它们不被9整除，也不含有数字9）

2. 输出

  每个测试用例输出一行 Case #x: y
   ·x：第x个用例（从1开始）
   ·y：该区间的合法数字个数（即不被九整除且不含9的数字的个数）

3. Limits

• 1 ≤ T ≤ 100.
• Time limit: 60 seconds per test set.
• Memory limit: 1 GB.
• F does not contain a 9 digit.
• F is not divisible by 9.
• L does not contain a 9 digit.
• L is not divisible by 9.

Small dataset (Test set 1 - Visible)

• 1 ≤ F < L ≤ 106.

Large dataset (Test set 2 - Hidden)

• 1 ≤ F < L ≤ 1018.

二、 解题思路

  我们要计算从F到L之间有多少个合法数据，可以转换成求从0到X之间有多少个合法数据 n u m ( X ) num(X) num(X)。那么从F到L之间就有 n u m ( L ) − n u m ( F ) + 1 num(L) - num(F) + 1 num(L)−num(F)+1个合法数据了。

  下面介绍求 n u m ( X ) num(X) num(X)的解法

  考虑一下不合法的数据，有两个条件：1) 不含数字9；2) 不能被9整除。

1. 对于第一个条件的解决

  既然数字中不能含有数字9，那我们把所有含有数字9的数去掉。剩下的数字仅由0~8这9位数字组成。
  我们将剩余的数字按顺序写出，如图1所示。剩下这些数字的排列完全等同于9进制数的排列（注：仍是十进制数，只是按照9进制排列以及进制转换可以计算该数的新位置）。

2. 对于第二个条件的解决

  去除所有含有数字9的数字以后，我们只需要考虑能否被9整除的问题了。
  对于数字X，我们写成如下形式
X = d n d n − 1 . . . d 0 X = d_{n}d_{n-1}...d_{0} X=dn​dn−1​...d0​
  那数字X在上图1中的哪个位置呢？我们可以将它单纯地看成9进制数，那么9进制在上图中的位置自然可以通过将其转化成十进制数来得到:
Y = ∑ i = 0 n d i ⋅ 9 i Y = \sum_{i=0}^{n}d_{i}\cdot 9^{i} Y=i=0∑n​di​⋅9i
  那么数字X是图一示意的新数据中的第 (Y + 1) 个数。

  懒得看文字的推导可以直接跳到 2.1 两个区间的划分，图形的解释更容易理解。

  用组的方式来表述X的位置是：第 (9a+b) 个数。
（例如数字11在图中的第二行第二个数，那么11 = 9*1 +2， 代表：满1组之后的第二个数字。）

  那么现在有
Y + 1 = 9 a + b Y + 1 = 9a + b Y+1=9a+b

  观察图一，每一列的末位 d 0 d_{0} d0​都是相等的，即b由 d 0 d_{0} d0​决定：
b = ( d 0 + 1 ) % 9 b = (d_{0} +1) \% 9 b=(d0​+1)%9

  所以当 d 0 = 8 d_{0} = 8 d0​=8时，刚好满整组（看图一也能直接看出来）。对于整组部分，每组有8个合法数字（每行不合法的数字分别时0，18，27，36，45，54，63，72，81）。
  对于不整组的部分，我们遍历一下，检查每一个数字是否能被9整除。
  对于 X X X，它是第 Y + 1 Y+1 Y+1个数字，那么对于 X − d 0 X-d_{0} X−d0​，它是第 Y − d 0 + 1 Y-d_{0}+1 Y−d0​+1个数字，剩下的从第 1 1 1 个数字到第 Y − d 0 Y-d_{0} Y−d0​ 个数字恰好为整组部分。共有组数为：
∑ i = 1 n d i ⋅ 9 i − 1 \sum_{i=1}^{n}d_{i}\cdot 9^{i-1} i=1∑n​di​⋅9i−1

2. 1 两个区间的划分

  按照上面的描述，我们将 [ 0 , X ] [0, X] [0,X]划为两个子区间
[ 0 , X − d 0 ) 和 [ X − d 0 , X ] [0, X-d_{0}) 和 [X-d_{0}, X] [0,X−d0​)和[X−d0​,X]
  第一个区间为整组的区间，第二个区间为不正组的区间。
  如图2所示，对于数字134，分成两个区间红色部分和蓝色部分： [ 0 , 128 ] [0, 128] [0,128] 和 [ 130 , 134 ] [130, 134] [130,134].

2. 2 对整组部分的处理

  共有多少整组呢。这完全可以由数字X除去最低位的其它位计算得到，即图3中绿色部分。组的数量a的计算：
a = ∑ i = 1 n d i ⋅ 9 i − 1 a = \sum_{i=1}^{n}d_{i}\cdot 9^{i-1} a=i=1∑n​di​⋅9i−1
  而每一组（即图中的每一行）均有8个合法数字（每行为连续9个数字，必有一个是能被9整除的，故每行合法数据有8个）。故整组部分的合法数字有res1个：
r e s = 8 × a = 8 × ∑ i = 1 n d i ⋅ 9 i − 1 res = 8 × a =8 × \sum_{i=1}^{n}d_{i}\cdot 9^{i-1} res=8×a=8×i=1∑n​di​⋅9i−1

2. 3 对非整组部分的处理

  非整组部分不超过8个数字，所以可以遍历一下，判断他们是否能被9整除.

  或者用 N % 9 > N % 10 N\%9 > N\%10 N%9>N%10 来判断数 X X X是否在图1中从对角线上方，若在从对角线¹上方，则没有能被9整除的数，则最终结果+1；否则仅为 N % 10 N\%10 N%10。非整数部分中的合法数字个数为：
N % 10 + ( N % 9 > N % 10 ) N\%10 + (N\%9 > N\%10) N%10+(N%9>N%10)

  当然也可以用 N % 9 < = N % 10 N\%9 <= N\%10 N%9<=N%10 来判断数 X X X是否在图1中从对角线下面或者正好在从对角线上（ X X X恰好能被9整除）。非整数部分中的合法数字个数为：
N % 10 + 1 − ( N % 9 < = N % 10 ) N\%10 + 1 - (N\%9 <= N\%10) N%10+1−(N%9<=N%10)

三、 代码描述

#include <string>
#include <cmath>
#include <iostream>

using namespace std;

typedef long long ll;

ll solve(ll N){
    ll res = 0;
        
    string N_str = to_string(N);
    int len = N_str.length();
    
    // 计算整组数量
    for(int i = 0; i < len-1; i++){
        res = res*9 + (N_str[i]-48); 
    }
    res *= 8;
    
    // 非整组部分处理方法1——遍历
    for(ll i = N - N%10; i <= N; i++)
        if(i%9 != 0)
            res++;
            
    // 非整组部分处理方法2
    //res += N%10 + (N%9 > N%10);

    return res;
}

int main(){
    int T;
    ll F, L, res;
    cin >> T;
    for(int i = 1; i <= T; i++)
    {
        cin >> F >> L;
        res = solve(L) - solve(F) + 1;
        cout << "Case #" << i << ": " << res <<endl;
    }
    
    return 0;
}