最小的倍数,只有0和4作为其数字

Question

给定数字A找到最小数字B,使得A*B仅包含数字4和0并且零仅应该在最后,即像404这样的数字无效.

例如:

| A | B   | A*B |
|---|-----|-----|
| 1 | 4   | 4   |
| 2 | 2   | 4   |
| 3 | 148 | 444 |
| 4 | 1   | 4   |
| 5 | 8   | 40  |

---

好吧,我以这种方式尝试了这个问题.保持整数队列.最小的数字是4.

Pop the number (i.e. the front element of the queue) and push the numbers that can be derived from this popped number. 
That is , when we pop 4, we push (4*10) = 40 and (4*10 + 4) = 44 with the constraint that the popped number is not divisible by 10. If it is, push only its next multiple of 10.

所以,我的队列将是:4,40,44,400,440,444,....

当我从队列中弹出元素时,我将检查它是否可以被给定的数字A整除.如果是,只需中断并弹出的数字是我想要的结果.

因为我的数字可能非常大,所以我维护了一个队列,pair<string,int>其中string对应于number和int对应的remainder.因此,可以容易地计算下一阶段的剩余部分.

例如:

queue : <"4",4> 
Pop , current result is string : "4" and remainder is lets say prev = 4
check if the last digit is 0 or not (for checking if its a multiple of 10 or not)
If not, then append 0 to this string and remainder as (prev*10)%a and push this pair in the queue. Also, append 4 to this string with remainder as : (prev*10 +4)%a and push. If the last digits is 0, append 0(not 4) and corresponding remainder, push this pair in the queue.

Queue: <"40",(prev*10)%a>, <"44", (prev*10 +4)%a> and so on..

直到队列前面的对为余数0,我们将继续这样做.

虽然这种改进似乎有点好,但不正确并没有通过所有测试用例.有人可以说明如何以最佳方式解决这个问题.(A的范围是10 ^ 10).

Answer 1

如果我理解了这个问题,解决方案必须匹配regualr表达式0 | 4 + 0*

它花了很多时间我不用C语言编程,但是下面的代码可以解决这个问题.

int calc( int n ) {
  int factor5;
  int factor2;
  int j;
  int a;
  int b;
  int i;

  /* trivial case 0 result is 0 */
  if( n==0 ) return 0;

  /* find the number of factors 2 and 5 in n */
  for( a=n, factor5=0; a%5==0; a/=5, factor5++ ); 
  for( a=n, factor2=0; a%2==0; a/=2, factor2++ ); 

  /* result is r=b*a where a=2^(j+2)*5^j */
  j=factor5;
  if( j < factor2-2 ) j=factor2-2; 

  for( a=4,i=0; i<j; i++, a*=10 ); 

  /* generate b in 1, 11, 111, ... until solution found */ 
  for( b=1; (a*b)%n!=0; b=10*b+1 );
  return a*b;
}

它可以测试:

int main ( void ) {
  int n,r;

  for( n=0; n<10; n++) {
    r=calc(n); printf( "n=%d r=%d\n", n, r );
  }

  return 0;
}

注意:优化它.Alsochange"int"到"long","long long"或使用任意长度整数的图书管理员.

测试:

n=0 r=0
n=1 r=4
n=2 r=4
n=3 r=444
n=4 r=4
n=5 r=40
n=6 r=444
n=7 r=444444
n=8 r=40
n=9 r=444444444

Rationalle:

除了具有结果0的普通情况0之外,结果"r"必须匹配正则表达式"4 + 0*":fours后跟零.也就是说,在正常的算术中,r = x*10 ^ j,其中x在4,44,444,....

如果我们提取因子4,我们有r = x*4*10 ^ j,其中x在序列1,11,111,...中.注意,这个序列中的数字从不是因子2和5(它们不是偶数,也不是0或5).

总之,r = x*2 ^(j + 2)*5 ^ j,其中x在1,11,111,......和"j"中从参数的因式分解中获得.程序的第一步是计算"j",接下来计算a = 2 ^(j + 2)*5 ^ j,最后生成序列1,11,111,...并测试它直到第一个有效结果.

Answer 2

我们将 40 号称为C，即C = A x B。

考虑到我所理解的限制，这是C = AxB由语言造成的4^n 0^m（不要将其理解为4功率n，它的意思是重复4 n次数），所以我们只需要n和 来m描述C。

观察结果：

1. 找到最小的B等于找到 的C倍数的最小A。
2. 当两个C数字的位数不同时，C位数越高的数字越大。
3. 当两个C数 的位数相等时n + m， sC的位数越大，则4越大。

因此，我们循环遍历 in 中的位数C（从 开始并递增），并以固定位数遍历a 中 s的1数目，再次从单个开始并递增。这为我们提供了按数字顺序排列的所有可能的 - 数字。4C4C

正如 @pasaba por aqui 的答案中所指出和使用的，可以通过利用A和C可能共享素因数这一事实来减少搜索空间。在这种情况下，每个C总是至少有素因数2( 2^2 = 4) 并且可能有5( 2*5 = 10)。

确实，C = x * 2^(j + 2) * 5^j与x in [1, 11, 111, ...]（即C = x * 4 * 10^j）。最小的j数等于中2或因子的最大数量。例如，如果、需要、如果、需要等等。5AA % 25 == 0j2A % 400 == 0j4

请参阅 pasaba por aqui 的答案以获取该解决方案。

暴力破解版：

#include <cstdint>
#include <iostream>


int
main(int, char *[])
{
    // use uintmax_t and hope that the number still fits.
    uintmax_t = 13ul; // or whatever

    for (unsigned k = 1u;; ++k) {
        // k is the number of digits
        for (unsigned m = 1u; m <= k; ++m) {
            // m is the number of 4s. 
            // We start at one 4 (zero does not make sense)
            uintmax_t C = 0u;
            // build C, add as many 4s as requested and
            // fill up with zeros
            for (unsigned i = 0; i < k; ++i) {
                if (i < m) {
                    C = C * 10 + 4;
                } else {
                    C = C * 10;
                }
            }
            // check if we have a multiple of A
            if (C % A == 0) {
                std::cout << "C = " << C << std::endl;
                std::cout << "B = " << (C / A) << std::endl;
                return 0;
            }
        }
    }

    return 1;
}