u014327136
yukangliu
采纳率66.7%
2016-04-28 03:34 阅读 2.2k

求7的整数倍和(大数算法)

3

求(1-10^18)内的整数,满足各位数字之和为7的整数倍的所有数的和,例如:25,86,106,1115各位相加都是7的整数倍。要求:1-2秒内完成

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

10条回答 默认 最新

  • lx624909677 lx624909677 2016-04-28 03:59

    你想高效的解决办法,就先贴出你写的认为不高效的代码,然后让大家帮你优化下

    点赞 1 评论 复制链接分享
  • m_912311697 m_912311697 2016-04-28 05:48

    我问了下大师,亚洲算法大赛银奖获得者,他说不可能办得到,你不用想了 楼主!

    点赞 1 评论 复制链接分享
  • u013427325 Daisy_1313 2016-04-28 03:36

    你把每一位数取余相加就可以了。

    点赞 评论 复制链接分享
  • m_912311697 m_912311697 2016-04-28 04:38

    这个问题用string去接收,然后遍历,相加除7(相加一定要是BigInteger类型)!也没有什么办法优化了,因为至少要遍历一遍

    点赞 评论 复制链接分享
  • m_912311697 m_912311697 2016-04-28 04:39

    错了是找出所有啊!!等等我想想

    点赞 评论 复制链接分享
  • u014327136 yukangliu 2016-04-28 04:46

    7,16,25,34,43,52,61,70,77,86。。。。这些数可能存在什么规律

    点赞 评论 复制链接分享
  • qq_26946497 谁用了我的英文名 2016-04-28 04:47

    也就是7进制嘛。
    找一个进位制转化的工具方法,然后做一个7进制数生成器,生成的值得规律是
    1,11,111,1111...

    点赞 评论 复制链接分享
  • u013427325 Daisy_1313 2016-04-28 05:03

    发现了一个误区,10^18这么大一个数的循环,至少也得循环10^18/7次,因为会有这么多数字满足条件,因此,1.2秒内不完成不了的,你觉得呢

    点赞 评论 复制链接分享
  • lx624909677 lx624909677 2016-04-28 11:07

    裴波那契数列递推公式:F(n+2) = F(n+1) + F(n)
    F(1)=F(2)=1.
    它的通项求解如下:
    F(n+2) = F(n+1) + F(n) => F(n+2) - F(n+1) - F(n) = 0
    令 F(n+2) - aF(n+1) = b(F(n+1) - aF(n))
    展开 F(n+2) - (a+b)F(n+1) + abF(n) = 0
    显然 a+b=1 ab=-1
    由韦达定理知 a、b为二次方程 x^2 - x - 1 = 0 的两个根
    解得 a = (1 + √5)/2,b = (1 -√5)/2 或 a = (1 -√5)/2,b = (1 + √5)/2
    令G(n) = F(n+1) - aF(n),则G(n+1) = bG(n),且G(1) = F(2) - aF(1) = 1 - a = b,因此G(n)为等比数列,G(n) = b^n ,即
    F(n+1) - aF(n) = G(n) = b^n --------(1)
    在(1)式中分别将上述 a b的两组解代入,由于对称性不妨设x = (1 + √5)/2,y = (1 -√5)/2,得到:
    F(n+1) - xF(n) = y^n
    F(n+1) - yF(n) = x^n
    以上两式相减得:
    (x-y)F(n) = x^n - y^n
    F(n) = (x^n - y^n)/(x-y) = {[(1+√5)/2]^n-[(1-√5)/2]^n}/√5

    点赞 评论 复制链接分享
  • qq_35067384 花谷 2016-05-20 15:53

    (1-10^18)之间的10^18,各位相加是1,肯定不是,那就是 17位,用字符串输入,一位的只有7,
    剩下的就是2-17位的,第一位是1-9,2-17位是0-9,前面的i-1为都是可以取任何组合,
    然后把前面的i-1位加起来,取余7,只有最后一位需要判断一下。
    如果刚刚求得的余数是0,则最后一位是0或7;
    如果刚刚求得的余数是1,2,3,4,则最后一位是7减去所求余数;
    如果刚刚求得的余数是5,6,则最后一位是7或14减去所求余数;

    点赞 评论 复制链接分享

相关推荐