2 u014327136 u014327136 于 2016.04.28 11:34 提问

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

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

10个回答

lx624909677
lx624909677   Ds   Rxr 2016.04.28 11:59

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

lx624909677
lx624909677 回复Daisy_1313: 溢出只是因为你使用了编译器自带的变量而已,题目已经说了,是使用大数算法了
一年多之前 回复
u013427325
u013427325 回复yukangliu: 兄弟,这个奇葩题哪里找到的,10…^18这么大的数,会溢出的,除非你用超级计算机啊,
一年多之前 回复
u014327136
u014327136 这题的高效率方案说白了就是找规律,找出通项公式,一般的算法面对10^18这样的数,都不行。一般方法就像楼上那位兄弟说的,求余相加就行。
一年多之前 回复
m_912311697
m_912311697   2016.04.28 13:48

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

u012817635
u012817635 ACM亚洲区银奖?
一年多之前 回复
qq_26946497
qq_26946497 回复Daisy_1313: 对啊,保持关注,有解答的话贴出来哦
一年多之前 回复
u013427325
u013427325 回复yukangliu: 楼主,想到解决办法,记得更新啊
一年多之前 回复
u013427325
u013427325 回复yukangliu: 遍历是不可能的,你得找个精通数学的人,得出一个什么结论,不是为难我们程序狗
一年多之前 回复
qq_26946497
qq_26946497 我去……数学上不可能?
一年多之前 回复
u014327136
u014327136 什么算法大赛?
一年多之前 回复
u013427325
u013427325   2016.04.28 11:36

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

u013427325
u013427325 这个确实有点难度,我回去帮你想想
一年多之前 回复
u014327136
u014327136 1-2秒内完成
一年多之前 回复
u014327136
u014327136 不是求解决方法,而是高效率解决方法
一年多之前 回复
m_912311697
m_912311697   2016.04.28 12:38

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

u014327136
u014327136 可以考虑求通项,7,16,25,34,43,52,61,70,77,86。。。这些数可能存在什么规律
一年多之前 回复
m_912311697
m_912311697   2016.04.28 12:39

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

u014327136
u014327136 好的
一年多之前 回复
u014327136
u014327136   2016.04.28 12:46

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

u014327136
u014327136 漏59
一年多之前 回复
qq_26946497
qq_26946497   2016.04.28 12:47

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

qq_26946497
qq_26946497 回复yukangliu: 对不起弄错了……
一年多之前 回复
u014327136
u014327136 各个位相加是7的倍数,不是数字为7的倍数;而且你说的应该是,10,110,1110。。。吧,这个方法应该比取余还慢
一年多之前 回复
u013427325
u013427325   2016.04.28 13:03

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

u014327136
u014327136 有一部分数是满足你说的,但像59,61都满足条件,相隔却是2,61,68则相隔7。所以加9加99加999。。。还是不行
一年多之前 回复
u014327136
u014327136 对,就是这样
一年多之前 回复
u013427325
u013427325 我也这么觉得,数量大概是这样的,
一年多之前 回复
qq_26946497
qq_26946497 回复Daisy_1313: 我也没找到数量的计算方法,在数学上应该是有近似计算公式的,不过数量级和你所说的是一致的。
一年多之前 回复
qq_26946497
qq_26946497 而是在构建的同时去直接执行最终目标:[的所有数的和]。应该是按位数来做。
一年多之前 回复
qq_26946497
qq_26946497 所以办法应该在于构建,把这一大堆数利用规律构建出来,然后没必要真的求出它们的值,因为那样肯定时间不满足要求。
一年多之前 回复
u013427325
u013427325 回复谁用了我的英文名: 那你说说,数量是多少
一年多之前 回复
qq_26946497
qq_26946497 我的看法是这样的。想要遍历去取,妥妥的不可以,因为就像你说的,数量太大,遍历本身就很耗时。
一年多之前 回复
qq_26946497
qq_26946497 额。在不发生更高级进位的情况下。就是增加9的时候百位不进位,增加99的时候千位不进位。应该很好理解把。
一年多之前 回复
qq_26946497
qq_26946497 数量不对。构建方法还是可以找到的。只要个位数不为0,并且这个数现在就满足条件,那么把这个数增加9,增加99,增加999等等,都符合条件。
一年多之前 回复
qq_26946497
qq_26946497 数量不对。构建方法还是可以找到的。只要个位数不为0,并且这个数现在就满足条件,那么把这个数增加9,增加99,增加999等等,都符合条件。
一年多之前 回复
lx624909677
lx624909677   Ds   Rxr 2016.04.28 19: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_26946497
qq_26946497 不太懂……这个和相加等于7的关系是什么呀
一年多之前 回复
qq_26946497
qq_26946497 不太懂……这个和相加等于7的关系是什么呀
一年多之前 回复
qq_35067384
qq_35067384   2016.05.20 23: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减去所求余数;

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!