4

如何找到 2 个数字 L 和 R（均包括在内）之间的数字计数，这些数字甚至具有数字的乘积？除了蛮力，我们还能怎么做呢？

dp[0][0]=4;
dp[0][1]=5;
for(int l=1;l<=9;l++)
{
    dp[l][0]=0;
    dp[l][1]=0;
    dp[l][0]+=(dp[l-1][0])*10;
    dp[l][0]+=dp[l-1][1]*5;
    dp[l][1]+=dp[l-1][1]*5;          
}

这是我制作的蛮力检查器，我正在尝试开发更有效的解决方案

bool f(ll n)
{
  ll p=1;
  if(n==0)
  return true;
  while(n)
  {
     p*=n%10;
     n/=10;
     if(p%2==0) return true;
     p=1;
  }
  if(p%2) return false;
  else
  return true;
}
ll brute(ll l,ll r)
{
   if(l>r) swap(l,r);
    ll cnt=0;
   for(ll  i=l;i<=r;i++)
   {
      if(f(i))
      {
         cnt++;
      }
   }

return cnt;

}

dp[l-1][0]存储长度为 l 的偶数产品编号这就是我的想法..？这能解决问题吗？

4

2 回答 2

3

蛮力是一种非常浪费的方法。我们可以做得更好。

（我为格式道歉；我希望内容仍然足够清晰。）

首先，让我们简化问题：

EvenProductNumbersBetween(RangeStart, RangeEnd) = NumbersBetween(RangeEnd - RangeStart) - AllOddDigitNumbersBetween(RangeStart, RangeEnd)

NumbersBetween(RangeStart, RangeEnd) = (RangeEnd - RangeStart) + 1

AllOddDigitNumbersBetween(RangeStart, RangeEnd) = AllOddDigitNumbersUpTo(RangeEnd) - AllOddDigitNumbersUpTo(RangeStart-1)

现在我们开始了：计算 AllOddDigitNumbersUpTo(RangeEnd)

首先，考虑简单的情况：

（假设 RangeEnd 为正）

如果 RangeEnd 是单个数字（即 < 10），则

AllOddDigitNumbersUpTo(RangeEnd) = Floor((RangeEnd+1)/2)

E.g.:
AllOddDigitNumbersUpTo(0) = {} = 0
AllOddDigitNumbersUpTo(1) = {1} = 1
AllOddDigitNumbersUpTo(2) = {1} = 1
AllOddDigitNumbersUpTo(3) = {1,3} = 2
AllOddDigitNumbersUpTo(4) = {1,3} = 2
AllOddDigitNumbersUpTo(5) = {1,3,5} = 3
AllOddDigitNumbersUpTo(6) = {1,3,5} = 3
AllOddDigitNumbersUpTo(7) = {1,3,5,7} = 4
AllOddDigitNumbersUpTo(8) = {1,3,5,7} = 4
AllOddDigitNumbersUpTo(9) = {1,3,5,7,9} = 5

如果 RangeEnd 可以是具有特定位数的任何数字，则

考虑到每个数字必须有五个奇数之一作为选择（前导零缩短长度，因此被排除在外），所以这很容易直接计算：

AllOddDigitNumbersOfLength(NumberLength) = 5^NumberLength

E.g.:
AllOddDigitNumbersOfLength(1) = {1, 3, 5, 7, 9} = 5
AllOddDigitNumbersOfLength(2) = {1, 3, 5, 7, 9} * {1, 3, 5, 7, 9} = 5*5 = 25
AllOddDigitNumbersOfLength(3) = 5*5*5 = 125
...

否则，将 RangeEnd 分开：

RangeEnd = (FirstDigit * 10^PowerOfFirstDigit) + Remainder

AllOddDigitNumbersUpTo(RangeEnd) = AllOddDigitNumbersUpTo(FirstDigit) * AllOddDigitNumbersOfLength(PowerOfFirstDigit-1) + AllOddDigitNumbersUpTo(Remainder)

不幸的是，前导零有一个复杂的情况。（感谢@AndyProwl 用我的答案的早期版本向我指出了这个问题！）如果余数以零开头，那么我们不应该在最后添加 AllOddDigitNumbersUpTo(Remainder) 项，因为受约束的前导零会使即使我们尝试制造的每一个较小的数字，该产品也是如此。

E.g.:

AllOddDigitNumbersUpTo(6300193) =
= AllOddDigitNumbersUpTo(6*(10^7) + 300193)
= AllOddDigitNumbersUpTo(6) * AllOddDigitNumbersOfLength(7-1) + AllOddDigitNumbersUpTo(300193)
= 3 * 5^6 + AllOddDigitNumbersUpTo(300193)
= Trivial * Trivial + LogarithmicallySmallerCase

AllOddDigitNumbersUpTo(300193) =
= AllOddDigitNumbersUpTo(3*(10^6) + 00193)
= AllOddDigitNumbersUpTo(3) * AllOddDigitNumbersOfLength(6-1)
= 2 * 5^5
= Trivial * Trivial
于 2013-01-24T20:52:39.597 回答
0

由于您可能必须检查每个数字，因此最短时间是线性 O(n)，所以我会使用蛮力，因为我认为没有算法可以解决。

于 2013-01-24T17:55:53.290 回答