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

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

10个回答

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

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

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

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

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

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

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

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

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

u014327136
yukangliu 好的
3 年多之前 回复

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

u014327136
yukangliu 漏59
3 年多之前 回复

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

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

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

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

裴波那契数列递推公式: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
谁用了我的英文名 不太懂……这个和相加等于7的关系是什么呀
3 年多之前 回复
qq_26946497
谁用了我的英文名 不太懂……这个和相加等于7的关系是什么呀
3 年多之前 回复

(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
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
求大数除法算法
大家有没有好的求大数除法的方法,思路。
一个求大数的算法
关于求大数的...........
求 大数开平方的算法?
请各位兄台指教
求:"5"的整数倍的正则表达式
如题 求:"5"的整数倍的正则表达式
大数算法之大数加减法
大数算法之大数加减法 当我们第一次编程,成功地在黑洞洞的控制台窗口中打印出“Hello World”的字符后,准备编写的第一个有实用性的程序是什么?我想,对于大多数人而言,这一问题的答案会是:四则运算器。C语言本身提供了四则运算的运算符+ - * /。因此写一个简单的加减乘除法程序可谓轻而易举。 Calculate A + B. 还有比这个更简单的C语言题目吗? #includ
求一个大数计算器的算法
类似Windows自带的计算器rn主要问题是大数的乘法除法的算法rnrn有源代码和思路皆可rnrn谢谢各位了!
求大数的阶乘的算法(java)
用java实现的求大数的阶乘 关键是用数组来存储计算结果
大数的算法
超大数据的算法,经典的算法,常用的算法,高效的算法
大数算法
目录 大数相加 大数相减 大数相乘 大数相除 大数相加 string add(string a,string b){ int temp=0;char c;string ans=""; while(a.size()>b.size())b='0'+b; // 补零 while(a.size()<b.size())a='0'+a; for(int i=0,j=a...
算法————大数减法,大数除法
算法————大数减法,大数除法[JAVA] 文章目录算法————大数减法,大数除法[JAVA]一.前言二.前置函数1.置后函数2.输出函数3.比较函数三.大数减法1.思想2.代码实现3.包装四.大数除法1.思想2.代码实现3.减法的改动 一.前言 在之间的时候,写了另一篇大数相关的算法:,后来一直忙于其他事,没有继续写大数其他的算法,现在就来看看大数其他算法的实现。 在之前的数据结构相关的博客里,...
求大数滑动窗口模幂算法
最近在研究大数运算,发现滑动窗口算法计算模幂很快,代码俺有,就是看不明白,不要论文,不要公式,只求算法流程。rn另外使用蒙哥马利算法虽然也可以求模幂,但是太慢啦!rnrn如果能弄懂该算法将另开贴送分。请大家帮忙。rnrn
求一个快速的大数求幂的算法
使用数组表示大数,如 123456789123456789123456789 这样的数,rn进行逻辑运算。rn现在要算 乘方,如 123456 的 123456 次方。rn有什么好的办法?rn我现在实现的是累乘,慢死了。rn1234 ^ 1234 在我的小奔腾双核上都能算一秒多……rn有什么快的算法没?求一个。rn
高分求大数(高精度)浮点运算算法
求高精度 浮点运算算法rn-.-!老师留的课程设计rn求2的开方精度1000位rn所以求对于浮点数的高精度算法(加,减,乘,除)rnC#,C都可以(禁用指针)rn
算法: 快速求中位数(第k大数)
#include #include int partition(int *a,int l,int r) { int i=l-1; int j=r,temp; int x=a[r]; while(1) { while(a[++i]<x); while(x<a[--j]) if(j==l) break; if(i>=j) break; temp=a[
算法笔记5067ProblemA 求第k大数
题目描述 给定一个长度为n(1≤n≤1,000,000)的无序正整数序列,以及另一个数k(1≤k≤1,000,000)(关于第k大的数:例如序列{1,2,3,4,5,6}中第3大的数是4。) 输入 第一行两个正整数m,n。 第二行为n个正整数。 输出 第k大的数。 样例输入 6 3 1 2 3 4 5 6 样例输出 4 代码展示 #include&lt;cstdio&gt; #include&lt...
求一个大数按位与的算法。。紧急求助
Dim a As StringrnDim b As Stringrna = "4294967297"rnb = "4294967296"rnMsgBox a And brn提示溢出。rnrn求一个可以处理大数按位与的算法。
求两个多位大数的最大公因数算法
求两个多位大数的最大公因数算法,C++语言编写(Maximum common factor of large numbers)
求一个精简的大数(字符串)算法
下面是我写的一个大数算法,虽然能跑,但是看起来比较混乱。rn那位大侠给个精简点的算法,顺便将算法的简要写明一下哈!!!(记得用C/C++格式写)rn在此谢过了。rn[code=C/C++]rnvoid Mult(char result[], const char i1[], const char i2[])rn rn int len1 = (int)strlen(i1);rn int len2 = (int)strlen(i2);rn int i, j, c = 0; rnrn for (i = 0; i < (len1 + len2); i++)rn rn int x = 0;rn for(j = len1 - 1; j >= 0; j--)rn rn int i1Index, i2Index;rn // 第一个数组取第N位,二个数组取第j-N位rn int N = j + 1;rn int M = (i + 1) + 1 - N;rn int u, v;rn rn if (N < 1 || N > len1 ||rn M < 1 || M > len2)rn rn continue;rn rn rn u = i1[len1 - N] - '0';rn v = i2[len2 - M] - '0';rn x = x + u * v;rn rn x = x + c;rn // 从数组最后一位开始存储值rn result[len1 + len2 - 1 - i] = x % 10 + '0';rn c = x / 10;rn rnrn[/code]
uva 1404 求很大数的素数算法
#include #include #define MAX(x,y) ((x)>(y)?(x):(y)) using namespace std; int prime[50050],cnt,vis[50050],ans[1000000]; bool flag[200000000]; void init(){ for(int i=2;i<=50000;i++){ if(!vis[i]){
求9/7小波算法
(本人有急用)谁有9/7小波的算法,请发给我啊,谢谢!不要是积分或卷积形式的,要具体的算法。邮箱ysdz@msn.com
大数素性测试+大数质因数分解(miller-rabin,Pollard_rho算法)
摘自kuangbin博客可以对一个2^63的素数进行判断。可以分解比较大的数的因子但是不明白一个地方是:大数质因子分解的出的数组factor[]的内容重复原因还有包含2,2不是质数啊?望大神赐教不过以后可以处理大数的素性判定了,还可以处理大数素因子分解了happy#include #include #include #include #include #include using namespac
大数算法——高精度大数幂次
大数——高精度大数求幂 Problems involving the computation of exact values of very large magnitude and precision are common. For example, the computation of the national debt is a taxing experience for many co
大数算法与组合数学算法
大数算法和组合数学算法 详细讲解了高等数学应用领域的算法
大数除法算法
大数除法
大数算法(大数相加)
这几天做projecteuler 发现数学很重要啊! 当计算非常大的数的相乘时,使用BigDecimal 便希望能自己实现大数的乘法 因为乘法里要使用加法,就先实现加法了 开始时,大数使用字符串保存 这时候我们需要将大数存储在一个数组里 为了节省空间,我们使用Byte存储每一位 [code=&quot;java&quot;] public static Byte[] StringToByte(St...
【NOIP算法】大数除法
我们这里研究的大数除法是:被除数是高精度数,除数是低精度数 分析 1)除法是从高位开始的,所以字符型被除数不用逆序转存到整数数组,顺序转存即可 2)余数*10+本位的数 作为下一个被除数 参考代码 #include &lt;iostream&gt; #include &lt;cstring&gt; using namespace std; #define N 200 in...
大数相除算法
简介在实际的项目中,同事在移植一个算法时候碰到要进行64位整数的除法运算。找了一下一下,Linux内核中有支持该运算的函数do_div(),该函数在 Linux/arch/arm/include/asm/div64.h 文件中实现。看不太懂其具体的实现方法,于是我就想能不能自己写一个大数相除的算法。下面就是算法的内容,如有不足之处,敬请指正。注:在以下公式以及代码中,名字的含义如下: m
算法 - RSA大数分解
Reading pager… Updated later
[跪求]大数XOR,NOT,AND,OR的算法
RT,哪位做过的给个思路都行.
算法-大数的四则运算
题目描述以加法为例 给出两个正整数A和B,计算A+B的值。保证A和B的位数不超过500位。 输入描述 Input Description 读入两个用空格隔开的正整数 输出描述 Output Description 输出A+B的值 样例输入 Sample Input 3 12 样例输出 Sample Output 15 大数加法 #include...
大数因数分解Pollard_rho 算法
大数分解最简单的思想也是试除法,这里就不再展示代码了,就是从2到sqrt(n),一个一个的试验,直到除到1或者循环完,最后判断一下是否已经除到1了即可。但是这样的做的复杂度是相当高的。一种很妙的思路是找到一个因子(不一定是质因子),然后再一路分解下去。这就是基于Miller_rabin的大数分解法Pollard_rho大数分解。Pollard_rho算法的大致流程是 先判断当前数是否是素数(Mill
C++程序设计——大数算法
C++程序设计—大数算法,内附代码(加减乘除四则运算),无需装软件即可运行;并附于代码分析和心得体会,全程任务,一步到位!!
大数的加减乘除的算法~
在8086汇编下怎么实现大数的加减乘除啊~,难道真的只有一位一位的算了?
征算法:大数除法。
各位大侠:rn 小弟在设计一个工程时遇到难题:rnrn 急需一个能进行 50 位 10 进制数除法运算的算法。rn 汇编程序最好。rn 谢谢!
算法之最大数问题
本次是一个整数,随意抽取其中的n个位置上的数值,求剩下的整数最大值是多少. 条件:整数    去掉n位   顺序不变    剩下的最大值 本题目又是一个将整型问题转化成字符串问题的经典案例,如果一个整数取出几位,保持最大,那么只要保证取出的位置的数值比前一位小就行了。 这个时候对应到字符串上就是取出某个位置的数值,而且该位置的数值比后一位的数值小。 比如原始整数是5263452,要求取出3
算法大数整数相加
大数整数加法 #include #include #include #include #include #include #include #include #include using namespace std;   #define MAXN 1000   int a[MAXN],b[MAXN];   int main(int argc, co
【NOIP算法】大数的加法
题目: 求两个不超过200位的非负整数的和 输入:有两行,每行是一个不超过200位的非负整数,可能有多余的前导0 输出:一行,即相加后的结果。结果里不能有多余的前导0,即如果结果是342,那么就不能输出为0342 【样例输入】 22222222222222222222222 3333333333333333333333 【样例输出】 55555555555555555555555 ...
大数的快速求余算法
大数的求余,相加,相减算法 A plus B+: Now give you two positive integers, A, B, and C. Please count A plus B, then modulo C. Input Input will consist of multiple problem instances. The first line of the in
关于大数加减乘除的算法
大数即很多位如几百位或几千位以上的数
大数计算器的算法问题
以前我写了一个大数计算器,用竖式的计算法,一共500多行rn加法减法还可以,乘法一般,除法的效率非常差(使用的是穷举算法,100000/2要6秒左右)rnrn现在打算:rn用归递法重写乘法部分和除法部分。rn要求:1.用到归递运算rn 2.实现不延时进行100位以外的运算rn 3.不可以进行超过3位数的内部运算rn 4.代码内容不可以超过80行(每一行只允许出现一个分号);rn 5.文件大小不可以超过80k;rn 6.使用+,-,*,/运算符一次运算的数据不超过1000(自己写的运算函数(如竖式进位)不限制) rnrn目前一点思路也没有,谁能提示一下?rnrn(Ps:本贴将会把以后的重写进展和遇到的问题贴出)rnrn---------------------rn冰蓝雪雨签名档rnrn欢迎加入C/CC++技术群:24109898
相关热词 c++和c#哪个就业率高 c# 批量动态创建控件 c# 模块和程序集的区别 c# gmap 截图 c# 验证码图片生成类 c# 再次尝试 连接失败 c#开发编写规范 c# 压缩图片好麻烦 c#计算数组中的平均值 c#获取路由参数