问题

Idea 1: Instead of looping through all numbers from a to b, you can optimize the process by considering the patterns of numbers containing 2, 5, or 8. For example, numbers like 2, 5, 8, 20-29, 50-59, 80-89, and so on will contain these digits. You can calculate how many of these patterns fit within the range [a, b] and then adjust for the remaining numbers within that range.

Idea 2: Use mathematical properties to calculate the count more efficiently. For example, you can calculate the count of numbers containing 2, 5, or 8 in the one's place, ten's place, hundred's place, and so on. Then, sum these counts to get the final result.

Idea 3: Utilize dynamic programming to optimize the counting process. You can build a table to store counts of numbers up to a certain length that contain 2, 5, or 8. Then, use this table to calculate the counts for larger numbers more efficiently.

These ideas can help you optimize your code to achieve the desired time limit of 1 second.

#include <stdio.h>
#include <conio.h>

int countDigit(long n) 
{ 
    int count = 0; 
    while (n != 0) {
		int num = n%10;
		if  (num == 2 || num == 5 || num == 8) {
			count++; 
		} 
        n = n / 10; 
    } 
    return count; 
}

int main() {
	long count = 0;
	for (int i = 11; i<= 100000; i++) {
		count += countDigit(i);	
	}
	
	printf("Count: %ld", count);
	
	return 0;
}

答案1

得分: 3

以下是您提供的内容的翻译：

在小于1毫秒内，100,000,000是多少？或者甚至在小于1毫秒内，100,000,000,000呢？

有一些事情可以注意到。

1. 十的幂次

对于10，结果是3，对于100 => 60，对于1000 => 900，...从一个幂次跳到下一个，我们会多计算3位数字2/5/8 10倍，加上低幂次的计数...这意味着从10到100，我们将初始的3乘以20，从100到1000，乘以300...

一般结果，对于10^n的数字是

R1 = 3 * n * 10^(n-1)

对于x * 10^n，其中x > 1，我们只需将R1乘以x，因为我们有x次。然后

• 如果x > 2，我们必须添加10^(n-1)（因为数字的右侧将重复出现2次），
• 如果x > 5，我们再次添加它（以便添加2次）
• 如果x > 8，再次（3次添加）

最后的情况是当x恰好是2或5或8时，在这种情况下，它将只“使用”一次（因为我们有x * 10^n），因此我们将结果加1。

2. 数字分解

我们还注意到一个数字dcba可以用以下方式表示：

a.10^0 + b.10^1 + c.10^2 + d.10^3

这并不是什么新鲜事。然而，更有趣的是

count(dcba) = count(a.10^0) + count(b.10^1) + count(c.10^2) + count(d.10^3)

这意味着通过分解我们的数字，我们可以使用我们的第一个计算规则，对于数字有多少位数。同样，如果d或c或b恰好是2或5或8，我们必须添加数字的右侧部分（因为我们必须“用尽”右侧部分）。例如，对于1234，我们将有

count(1000) + count(200) + [34] + count(30) + count(4)

基于数字位数的算法复杂度是（以10为底的对数）

O(log(n))

3. 程序

在下面的C程序中，负责计算10的幂次的函数将为54321调用5次。应该小于1毫秒！（我使用了/usr/bin/time）

（使用long类型以允许更大的数字）

long count1(int d, int tens) {
     long power = 1;
     for(int p=0 ; p<tens ; p++) power *= 10; // 10^tens
     long powerless = power / 10;             // 10^(tens-1)
     long one = 3 * tens * powerless;
     long r = d * one;
     if (d > 2) r += power;  // 添加2
     if (d > 5) r += power;  // 添加5
     if (d > 8) r += power;  // 添加8
     if (d == 2 || d == 5 || d == 8) r ++; // 如果恰好为2/5/8则添加1
     return r;
}

long count(long n) {
     long res = 0;
     int tens = 0;       // log10(n)
     long power = 1;     // 10^tens
     long remainder = 0; // 数字的右侧部分
     while (n) {         // 分解n
          int d = n % 10;
          if (d) {
                res += count1(d, tens);
                if (d == 2 || d == 5 || d == 8) {
                     res += remainder;
                }
          }
          remainder += d * power;
          tens ++;
          power *= 10;
          n /= 10;
     }
     return res;
}

用法：从`a`到`b`

long result = count( b );
if (a > 1) result -= count ( a-1 ); // 减去`a-1`的结果

示例：从11到...

100,000,000 => 239999997
100,000,000,000 => 329999999997
100,000,000,000,000 => 419999999999997（花费了1毫秒）

    100,000,000 in < 1 millisecond, or even
100,000,000,000 in < 1 millisecond also?

R1 = 3 * n * 10^(n-1)

a.10^0 + b.10^1 + c.10^2 + d.10^3

count(dcba) = count(a.10^0) + count(b.10^1) + count(c.10^2) + count(d.10^3)

count(1000) + count(200) + [34] + count(30) + count(4)

O(log(n))

long count1(int d, int tens) {
long power = 1;
for(int p=0 ; p<tens ; p++) power *= 10; // 10^tens
long powerless = power / 10;             // 10^(tens-1)
long one = 3 * tens * powerless;
long r = d * one;
if (d > 2) r += power;  // Add the 2s
if (d > 5) r += power;  // the 5s
if (d > 8) r += power;  // the 8s
if (d == 2 || d == 5 || d == 8) r ++; // Add 1 if exactly 2/5/8
return r;
}
long count(long n) {
long res = 0;
int tens = 0;       // log10(n)
long power = 1;     // 10^tens
long remainder = 0; // Right part of number
while (n) {         // Breakdown n
int d = n % 10;
if (d) {
res += count1(d, tens);
if (d == 2 || d == 5 || d == 8) {
res += remainder;
}
}
remainder += d * power;
tens ++;
power *= 10;
n /= 10;
}
return res;
}

long result = count( b );
if (a > 1) result -= count ( a-1 ); // subtract result for `a-1`

        100,000,000 => 239999997
100,000,000,000 => 329999999997
100,000,000,000,000 => 419999999999997  (took 1 millisecond)

答案2

得分: 1

为了确定范围[a，b]中数字2、5和8的数量，您只需确定范围[0，l]中这些数字的数量。然后，您可以通过从范围[0，a-1]中数字的数量减去范围[0，b]中数字的数量来确定范围[a，b]中数字的数量。

在范围[0，l]中数字的数量可以更容易地确定，方法是将l分解为10的幂值的和。例如，范围[0，234]中数字的数量等于范围[0，200]中数字的数量加上范围[1，30]中数字的数量再加上范围[1，4]中数字的数量。幸运的是，范围[1，L]中数字的数量与[0，L]中的数量相同，因为值0的数量值为0。

因此，问题被简化为确定范围内的数字10的值Dx10^N中数字的数量，其中D在0到9的范围内，N在0到8的范围内。让C(D,N)表示范围[0，Dx10^N]中数字的数量。

我们可以轻松手工推导出C(D,0)的值：(0:0, 1:0, 2:1, 3:1, 4:1, 5:2, 6:2, 7:2, 8:3, 9:3)。通过使用初始程序，我们还可以确定不同D的C(D,1)的值：(0:0, 1:3, 2:7, 3:19, 4:22, 5:26, 6:38, 7:41, 8:45, 9:57)。我们可以看到这些数字中存在一种模式：(0:0=0x3+0, 1:3=1x3+0, 2:7=2x3+1, 3:19=3x3+10, 4:22=4x3+10, 5:26=5x3+10+1, 6:38=6x3+2x10, 7:41=7x3+2x10, 8:45=8x3+2x10+1, 9:57=9x3+3x10)。因此，对于D=1的情况，这个值是相关的。在这种情况下，它是3，但对于更大的N，这个值G(N)=3xNx10^(N-1)。例如，对于10000，N=4，G(4)=12000=3x4x10^3。您可以使用范围[0，10000]的初始程序验证这个值。

上限为L=Dx10^N的幂10值的数字数量为C(D,N)=DxG(N)+K(D,N)。当N=1时，我们有G(1)=3。根据我们之前找到的模式，我们可以推导出以下K(D,1)值（0:0, 1:0, 2:1, 3:10, 4:10, 5:11, 6:20, 7:20, 8:21, 9:30）。例如，对于60，C(6,1)=6x3+20=38。

从而，通过再次使用初始程序，我们可以推导出K(D,N)的一般函数。例如，当N=3时，我们有G(3)=3x3x10^2=900。使用程序，我们得到3000的C(3,3)=3700=3x900+1000。因此，不同值的D（0:0, 1:0, 2:1, 3:10^N, 4:10^N, 5:1+10^N, 6:2x10^N, 7:2x10^N, 8:1+2x10^N, 9:3x10^N），函数K(D,N)如下定义。我们可以使用范围[0, 8000]的数字数量验证这个值，得到9201。C(8,3)=8xG(3)+K(8,3)=8x900+2001=9201。

现在，我们拥有计算数字数量的所有要素。首先，我们必须创建一个函数，计算范围[0，L]中数字2、5和8的数量，其中L是10的幂值以获取值C(D,N)。为此，我们需要计算G(N)和K(D,N)。

然后，我们将给定的边界L分解为幂10值的和，计算每个范围中数字数量的总和。

以下是程序：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// power10返回10^n。要求n >= 0 && n < 9。
int power10(int n) {
    static int tbl[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};
    return tbl[n];
}

// count_digits_in_power10返回范围[0, d*10^n]中数字2、5和8的数量。
// 要求d在范围[0,9]，n在范围[1,8]内。
int count_digits_in_power10(int d, int n) {
    int g = 3*n*power10(n-1);
    switch(d) {
        case 0:
            return 0;
        case 1:
            return g;
        case 2:
            return 2*g + 1;
        case 3:
            return 3*g + power10(n);
        case 4:
            return 4*g + power10(n);
        case 5:
            return 5*g + power10(n) + 1;
        case 6:
            return 6*g + 2*power10(n);
        case 7:
            return 7*g + 2*power10(n);
        case 8:
            return 8*g + 2*power10(n) + 1;
        case 9:
            return 9*g + 3

<details>
<summary>英文:</summary>

To determine the count of digits 2,5 and 8 in the range [a,b], you need only to determine the count of those digits in the range [0,l]. You then determine the count of digits in the range [a,b] by subtracting the count of digits in the range [0,a-1] from the count of digits in the range [0,b].

The count of digits in the range [0,l] can be determined more easily by decomposing l in a sum of power 10 values. For instance, the count of digits in the range [0,234] is the count of digits in the range [0,200] + the count of digits in the range [1,30] + the count of digits in the range [1,4]. Luckily, the count of digits in the range [1,L] is the same as in [0,L] since the value 0 has a count value of 0. 

The problem is thus reduced into determining the count of digits in the power 10 value Dx10^N with D in the range 0 to 9 and N in the range 0 to 8. Let C(D,N) be the count of digits in the range [0, Dx10^N].

We can easily deduce by hand C(D,0) : (0:0, 1:0, 2:1, 3:1, 4:1, 5:2, 6:2, 7:2, 8:3, 9:3). By using the initial program we can also determine the values C(D,1) for the different D : (0:0, 1:3, 2:7, 3:19, 4:22, 5:26, 6:38, 7:41, 8:45, 9:57). We can see a pattern in these numbers: (0:0=0x3+0, 1:3=1x3+0, 2:7=2x3+1, 3:19=3x3+10, 4:22=4x3+10, 5:26=5x3+10+1, 6:38=6x3+2x10, 7:41=7x3+2x10, 8:45=8x3+2x10+1, 9:57=9x3+3x10). The value with D=1 is thus a relevant value. In this case it is 3, but with bigger N, this value G(N)=3xNx10^(N-1). For instance for 10000, N=4 and G(4)=12000=3x4x10^3. You can verify this value with the initial program for the range [0, 10000].

The counts of digits for a power 10 upper limit L=Dx10^N is then C(D,N)=DxG(N)+K(D,N). When N=1, we have G(1)=3. Using the pattern we found before, we deduce the following K(D,1) values (0:0, 1:0, 2:1, 3:10, 4:10, 5:11, 6:20, 7:20, 8:21, 9:30). For instance, for 60, C(6,1)=6x3+20=38. 

From this, and by probing again with the initial program, we deduce the general function K(D,N). For instance, when N=3, we have G(3)=3x3x10^2=900. Using the program we get for 3000 C(3,3)=3700=3x900+1000. The function K(D,N) is thus defined as follow for the different value of D (0:0, 1:0, 2:1, 3:10^N, 4:10^N, 5:1+10^N, 6:2x10^N, 7:2x10^N, 8:1+2x10^N, 9:3x10^N). We can verify with the count of digits in the range [0, 8000] which yields 9201. C(8,3)=8xG(3)+K(8,3)=8x900+2001=9201.

We now have all the pieces of the puzzle to compute the count of digits. We must first create a function that computes the number of digits 2, 5 and 8 in the range [0,L] where L is a power 10 value to get the value C(D,N). For this we need to compute G(N) and K(D,N). 

We then decompose a given boundary L in a sum of power 10 values and compute the sum of count of digits in each range. 

Here is the program:

```c
#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;assert.h&gt;

// power10 returns 10^n. Requires n &gt;= 0 &amp;&amp; n &lt; 9. 
int power10(int n) {
	static int tbl[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};
	return tbl[n];
}

// count_digits_in_power10 return the number of digits 2,5 and 8 in the range [0, d*10^n].
// Requires d is in the range [0,9] and n is in the range [1,8].
int count_digits_in_power10(int d, int n) {
	int g = 3*n*power10(n-1);
	switch(d) {
	case 0:
	    return 0;
	case 1:
	    return g;
	case 2:
	    return 2*g + 1;
	case 3:
	    return 3*g + power10(n);
	case 4:
	    return 4*g + power10(n);
	case 5:
	    return 5*g + power10(n) + 1;
	case 6:
	    return 6*g + 2*power10(n);
	case 7:
	    return 7*g + 2*power10(n);
	case 8:
	    return 8*g + 2*power10(n) + 1;
	case 9:
	    return 9*g + 3*power10(n);
	}
}

// count_digits_to_limit returns the number of digits 2,5 and 8 in the range [0,l].
// Requires l is in the range [0, 100000000].
int count_digits_to_limit(int l) {
    assert(l &gt;= 0 &amp;&amp; l &lt;= 100000000);
    int c = 0;
	for(int n = 8; n &gt; 0; n--) {
		int p = power10(n);
		int d = l/p;
		assert(d &gt;= 0 &amp;&amp; d &lt;= 9);
		if (d &gt; 0) {
			c += count_digits_in_power10(d, n);
			l -= d*p;
		}
	}
    assert(l &gt;= 0 &amp;&amp; l &lt;= 9);
    if (l &lt; 2)
        return c;
    if (l &lt; 5)
        return c+1;
    if (l &lt; 8)
        return c+2;
    return c+3;
}


int main() {
    int a, b;
    printf(&quot;bound a: &quot;);
    scanf(&quot;%d&quot;, &amp;a);
    if (a &lt; 0 || a &gt; 100000000) {
    	printf(&quot;a is invalid: %d\n&quot;, a);
    	return 1;
    }
    printf(&quot;bound b: &quot;);
    scanf(&quot;%d&quot;, &amp;b);
    if (b &lt; 0 || b &gt; 100000000) {
    	printf(&quot;b is invalid: %d\n&quot;, b);
    	return 1;
    }
    if (a &gt; b) {
    	printf(&quot;a (%d) is bigger than b (%d)\n&quot;, a, b);
    	return 1;
    }
    int c = count_digits_to_limit(b);
    if (a &gt; 0)
	    c -= count_digits_to_limit(a-1);
    printf(&quot;count of digits 2,5 and 8 in range [%d, %d] is %d\n&quot;, a, b, c);
    
    return 0;	
}

Here is the output:

bound a: 11
bound b: 100000
count of digits 2,5 and 8 in range [11, 100000] is 149997