草庐IT

c++ - 只有 0 和 4 作为数字的最小倍数

coder 2023-06-01 原文

给定一个数字 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> 的队列其中字符串对应于 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)。

最佳答案

如果我理解问题，解决方案必须匹配正则表达式 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;
}

注意:优化一下。还将“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

理由:

除了结果为 0 的普通情况 0 之外，结果“r”必须匹配正则表达式“4+0*”:四后跟零。也就是说，在普通算术中， 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,...并测试直到第一个有效结果。

关于c++ - 只有 0 和 4 作为数字的最小倍数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32055740/

amp43codefactorsectionc++algorithm

有关c++ - 只有 0 和 4 作为数字的最小倍数的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. ruby - RSpec - 使用测试替身作为 block 参数 - 2

    我有一些Ruby代码，如下所示:Something.createdo|x|x.foo=barend我想编写一个测试，它使用double代替block参数x，这样我就可以调用:x_double.should_receive(:foo).with("whatever").这可能吗？ 最佳答案 specify'something'dox=doublex.should_receive(:foo=).with("whatever")Something.should_receive(:create).and_yield(x)#callthere

  3. ruby - 查找字符串中的内容类型(数字、日期、时间、字符串等) - 2

    我正在尝试解析一个CSV文件并使用SQL命令自动为其创建一个表。CSV中的第一行给出了列标题。但我需要推断每个列的类型。Ruby中是否有任何函数可以找到每个字段中内容的类型。例如，CSV行:"12012","Test","1233.22","12:21:22","10/10/2009"应该产生像这样的类型['integer','string','float','time','date']谢谢! 最佳答案 require'time'defto_something(str)if(num=Integer(str)rescueFloat(s

  4. ruby - 字符串文字中的转义状态作为 `String#tr` 的参数 - 2

    对于作为String#tr参数的单引号字符串文字中反斜杠的转义状态，我觉得有些神秘。你能解释一下下面三个例子之间的对比吗？我特别不明白第二个。为了避免复杂化，我在这里使用了'd'，在双引号中转义时不会改变含义("\d"="d")。'\\'.tr('\\','x')#=>"x"'\\'.tr('\\d','x')#=>"\\"'\\'.tr('\\\d','x')#=>"x" 最佳答案 在tr中转义tr的第一个参数非常类似于正则表达式中的括号字符分组。您可以在表达式的开头使用^来否定匹配(替换任何不匹配的内容)并使用例如a-f来匹配一

  5. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  6. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  7. ruby-on-rails - 应用程序的名称是否可以作为变量使用？ - 2

    当我创建一个Rails应用程序时，控制台:railsnewfoo我的代码可以使用字符串“foo”吗？puts"Yourapp'snameis"+app_name_bar 最佳答案 Rails.application.class将为您提供应用程序的全名(例如YourAppName::Application)。从那里您可以使用Rails.application.class.parent获取模块名称。 关于ruby-on-rails-应用程序的名称是否可以作为变量使用？，我们在StackOve

  8. ruby - 获取数组中的值并最小化某个类属性的最优雅的方法是什么？ - 2

    假设我有以下类(class):classPersondefinitialize(name,age)@name=name@age=ageenddefget_agereturn@ageendend我有一组Person对象。是否有一种简洁的、类似于Ruby的方法来获取最小(或最大)年龄的人？如何根据它对它们进行排序？ 最佳答案 这样做会:people_array.min_by(&:get_age)people_array.max_by(&:get_age)people_array.sort_by(&:get_age)

  9. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  10. ruby-on-rails - 使用作为方法的值在 ruby​​ 中搜索哈希 - 2

    我在搜索我的值是方法的散列时遇到问题。我只是不想运行plan_type与键匹配的方法。defmethod(plan_type,plan,user){foo:plan_is_foo(plan,user),bar:plan_is_bar(plan,user),waa:plan_is_waa(plan,user),har:plan_is_har(user)}[plan_type]end目前如果我传入“bar”作为plan_type，所有方法都会运行，我怎么能只运行plan_is_bar方法呢？ 最佳答案 这个变体怎么样？defmethod

随机推荐