算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
数学家们喜欢各种类型的有奇怪特性的数。例如,他们认为945是一个有趣的数,因为它是第一个所有约数之和大于本身的奇数。
本次的题目正确率可是低到了一个境界呢!快来试试吧! 题目描述 正整数x 的约数是能整除x 的正整数。正整数x 的约数个数记为div(x)。例如,1,2, 5,10 都是正整数10 的约数,且div(10)=4。设a 和b 是2 个正整数,a≤b,找出a 和b 之间约数个数最多的数x 输入 输入2 个正整数a≤b,编程计算a 和b 之间约数个数最多的数。 输出 程序运行结束时,找到a 和b 之间约数个数最多的数是x,将div(x)输出 样例输入 1 36 样例输出 9 PS:如果你有想法或者想
约数和质数一样在蓝桥杯考试中是在数论中考察频率较高的一种,在省赛考察的时候往往就是模板题,难度大一点会结合其他知识点考察,但是仍然会用到模板,这里有三大模板,第一个是试除法求约数个数,第二个是求约数个数,第三个是求约数的和(来自y总的三个模型)
首先想到最简单的方法就是暴力求解就可以。当然数据小、或者测试数据少就很简单就可以过了。
链接:https://www.nowcoder.com/acm/contest/90/F 来源:牛客网
链接:https://www.nowcoder.com/acm/contest/90/F 来源:牛客网 1.题目描述 给定n,求1/x + 1/y = 1/n (x<=y)的解数。(x、y、n均为正整数) 输入描述: 在第一行输入一个正整数T。 接下来有T行,每行输入一个正整数n,请求出符合该方程要求的解数。 (1<=n<=1e9) 输出描述: 输出符合该方程要求的解数。 示例1 输入 3 1 20180101 1000000000 输出 1
初始时有 n 个灯泡关闭。 第 1 轮,你打开所有的灯泡。 第 2 轮,每两个灯泡你关闭一次。 第 3 轮,每三个灯泡切换一次开关(如果关闭则开启,如果开启则关闭)。第 i 轮,每 i 个灯泡切换一次开关。 对于第 n 轮,你只切换最后一个灯泡的开关。 找出 n 轮后有多少个亮着的灯泡。
主要思想:定义变量,使其在小于传入判断值的条件下从 1 开始自增,如果判断值和该变量进行模取运算后的值为 0,则说明该变量此时的值是判断值得一个约数。那么,程序计数器自增,记录下此值。循环结束后,输出计数器保存的值即为判断值约数的个数
N=p^{\alpha _{1}}*p^{\alpha _{2}}*...*p^{\alpha _{k}}
罗列出每个数,依次删除每个数的倍数,剩下的数就是质数,可以对此进行优化,可以不删每一个数的倍数, 可以只删质数的倍数,这样就不用重复删。
假设$n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$
拿到题目,我们首先做的要理解清除题目含义,对于从未听过的陌生概念、术语(一般会举例说明),我们也要试着首先理解示例
题目描述 科学家们在Samuel星球上的探险得到了丰富的能源储备,这使得空间站中大型计算机“Samuel II”的长时间运算成为了可能。由于在去年一年的辛苦工作取得了不错的成绩,小联被允许用“Samu
if elif else,for break continue pass,应该都见过,for else 和 while else组合的语句很少见,可用的场景也不多,但是了解他们的原理还是很有必要的,说不定哪天就可以用上了。
令 C(n) 表示 把 n 拆分成 a\times b=n(a\leq b) 且 a,b 的因子个数相同的方案数 给定一个整数n,(1 \leq n \leq 100)。 求出C(n!)。
约瑟夫问题的升级版,每次出去的是前一个出去的人位置+手上的数字(正往前,负往后)。第i个出去的人拿的糖是i的约数的个数。求拿糖最多的人和他的糖果数。
判断一个数字是否是质数,就是看它的因子是否只有1和它本身。质数的判断我们简单写个函数判断就行,代码如下,遍历的时候不需要从2到n,只需要遍历到n的平方根即可。
线性筛素数 保证每个数只会被它的最小质因子给筛掉(不同于埃氏筛中每个数会被它所有质因子筛一遍从而使复杂度过高)
60 = 2^2 * 3^1 * 5^1 则60的因子数有(2+1) * (1+1) * (1+1) = 12个
题目描述 设d(x)为x的约数个数,给定N、M,求 \sum^N_{i=1}\sum^M_{j=1}d(ij)∑i=1N∑j=1Md(ij) 输入输出格式 输入格式: 输入文件包含多组测试数据。第一行,一个整数T,表示测试数据的组数。接下来的T行,每行两个整数N、M。 输出格式: T行,每行一个整数,表示你所求的答案。 输入输出样例 输入样例#1: 2 7 4 5 6 输出样例#1: 110 121 说明 1<=N, M<=50000 1<=T<=50000 有一个定理 然后大力推公式就好了
我们提前设置一个标记数组prime[N] ,提前标记好数字的质数状态,这样就能减少重复判断。
Problem A: 回文 Time Limit: 1 Sec Memory Limit: 128 MB Submit: 1719 Solved: 528 Description 小王想知道一个字符串是否为ABA’型字符串。ABA’型字符串的定义:S=ABA’,A,B,A’都是原字符串的子串(不能是空串),A’的意思是A的反转串,B不一定要和A或A’不同。符合ABA’型的例如:"aba”,"acbbca”,"abcefgcba”等。"Abcefgcba”是ABA’型,因为它能找到一组对应的A("abc”
这里在贴一下部分评測数据,为什么是部分呢?由于是在非常多台电脑上跑的。丢了一些。可是肯定跑全了!
给定一个长为 n 的序列,有 m 次查询,每次查询一段区间的乘积的约数个数 \bmod 19260817 的值。
\[\sum_{i = 1}^n \sum_{j = 1}^m \sigma(gcd(i, j))\]
第十一届蓝桥杯大赛个人赛校内选拔(软件类)题目:https://blog.csdn.net/qq262593421/article/details/111598726
输入包含多组测试用例。 每组测试数据首先是一个正整数N,表示本组数据有N个整数。 请处理到文件结束。
输出格式 共 n 行,其中第 i 行输出第 i 个正整数 ai 是否为质数,是则输出 Yes,否则输出 No。
所以我们只需要预处理出 F(x)=\sum\limits_{i=1}^x\lfloor \frac{x}{i} \rfloor 即可。
考察计算机基础知识,所谓集成电路是将大量的晶体管和电子线路组合在一块硅片上,故又称为芯片。故选 A A A。
项目链接:https://github.com/jackfrued/Python-100-Days
为了解决重复代码的问题,我们可以封装重复的代码到“函数”的功能模块中,在需用使用该功能的地方,我们只需要“调用”这个“函数”就可以了。
小易是一个数论爱好者,并且对于一个数的奇数约数十分感兴趣。一天小易遇到这样一个问题: 定义函数f(x)为x最大的奇数约数,x为正整数。 例如:f(44) = 11. 现在给出一个N,需要求出 f(1) + f(2) + f(3).......f(N) 例如: N = 7 f(1) + f(2) + f(3) + f(4) + f(5) + f(6) + f(7) = 1 + 1 + 3 + 1 + 5 + 3 + 7 = 21 小易计算这个问题遇到了困难,需要你来设计一个算法帮助他。
2)在64位机上,char *p= “abcdefghijk”; sizeof§大小为12
定义函数:def 关键字。函数名后面的圆括号中可以放置传给函数的参数,函数执行完成后可以通过 return 关键字来返回一个值。
又是我们的OJ 题目链接: http://www.cn210.com/onlinejudge/problemshow.php?pro_id=92 Description tancu likes spa
闭包(Closure)是词法闭包(Lexical Closure)的简称,是引用了自由变量的函数。这个被引用的自由变量将和这个函数一同存在,即使已经离开了创造它的环境也不例外
2021-05-31:怎么判断n个数俩俩互质?比如7,8,9任意两个数最大公约数是1,所以7,8,9两两互质。比如8,9,10不是两两互质,因为8和10的最大公约数是2。
给定一个表示分数加减运算的字符串 expression,你需要返回一个字符串形式的计算结果。
python3.X版本的请点击这里25行代码实现完整的RSA算法 网络上很多关于RSA算法的原理介绍,但是翻来翻去就是没有一个靠谱、让人信服的算法代码实现,即使有代码介绍,也都是直接调用JDK或者Python代码包中的API实现,也有可能并没有把核心放在原理的实现上,而是字符串转数字啦、或者数字转字符串啦、或者即使有代码也都写得特别烂。无形中让人感觉RSA加密算法竟然这么高深,然后就看不下去了。看到了这样的代码我就特别生气,四个字:误人子弟。还有我发现对于“大整数的幂次乘方取模”竟然采用直接计算的幂次的值,再取模,类似于(2 ^ 1024) ^ (2 ^ 1024),这样的计算就直接去计算了,我不知道各位博主有没有运行他们的代码???知道这个数字有多大吗?这么说吧,把全宇宙中的物质都做成硬盘都放不下,更何况你的512M内存的电脑。所以我说他们的代码只可远观而不可亵玩已。 于是我用了2天时间,没有去参考网上的代码重新开始把RSA算法的代码完全实现了一遍以后发现代码竟然这么少,基本上25行就全部搞定。为了方便整数的计算,我使用了Python语言。为什么用Python?因为Python在数值计算上比较直观,即使没有学习过python的人,也能一眼就看懂了代码。而Java语言需要用到BigInteger类,数值的计算都是用方法调用,所以使用起来比较麻烦。如果有同学对我得代码感兴趣的话,先二话不说,不管3X7=22,把代码粘贴进pydev中运行一遍,是驴是马拉出来溜溜。看不懂可以私信我,我就把代码具体讲讲,如果本文章没有人感兴趣,我就不做讲解了。 RSA算法的步骤主要有以下几个步骤: 1、选择 p、q两个超级大的质数 ,都是1024位,显得咱们的程序货真价实。 2、令n = p * q。取 φ(n) =(p-1) * (q-1)。 计算与n互质的整数的个数。 3、取 e ∈ 1 < e < φ(n) ,( n , e )作为公钥对,正式环境中取65537。可以打开任意一个被认证过的https证书,都可以看到。 4、令 ed mod φ(n) = 1,计算d,( n , d ) 作为私钥对。 计算d可以利用扩展欧几里的算法进行计算,非常简单,不超过5行代码就搞定。 5、销毁 p、q。密文 = 明文 ^ e mod n , 明文 = 密文 ^ d mod n。利用蒙哥马利方法进行计算,也叫反复平方法,非常简单,不超过10行代码搞定。 实测:秘钥长度在2048位的时候,我的thinkpad笔记本T440上面、python2.7环境的运行时间是0.035秒,1024位的时候是0.008秒。说明了RSA加密算法的算法复杂度应该是O(N^2),其中n是秘钥长度。不知道能不能优化到O(NlogN) 代码主要涉及到三个Python可执行文件:计算最大公约数、大整数幂取模算法、公钥私钥生成及加解密。这三个文件构成了RSA算法的核心。 这个时候很多同学就不干了,说为什么我在网上看到的很多RSA理论都特别多,都分很多个章节,在每个章节中,都有好多个屏幕才能显示完,这么多的理论,想想怎么也得上千行代码才能实现,怎么到了你这里25行就搞定了呢?北门大官人你不会是在糊弄我们把?其实真的没有,我是良心博主,绝对不会糊弄大家,你们看到的理论确实这么多,我也都看过了,我把这些理论用了zip,gzip,hafuman,tar,rar等很多的压缩算法一遍遍地进行压缩,才有了这个微缩版的rsa代码实现,代码虽少,五脏俱全,是你居家旅行,课程设计、忽悠小白、必备良药。其实里边的几乎每一行代码都能写一篇博客专门进行介绍。 前方高能,我要开始装逼了。看不懂的童鞋请绕道,先去看看理论,具体内容如下: 1. 计算最大公约数 2. 超大整数的超大整数次幂取超大整数模算法(好拗口,哈哈,不拗口一点就显示不出这个算法的超级牛逼之处) 3. 公钥私钥生成
辗转相除法, 又名欧几里德算法(Euclidean algorithm),是求最大公约数的一种方法。它的具体做法是:
我们这里只看最大公约数,很多家长在陪同孩子做作业的时候就会遇到这个问题,孩子问你,这两个数的最大公约数是什么,你就要拿起纸笔来计算了,简单的还好,能被2/3整除的这类可以利用成倍的数值测试,几秒也就算出来了,但是很多的时候甚至是比较大的质因数,就很难通过大脑直接运算了,不过我们很多时候还是身边有计算机的,那么使用这个工具跑起来就方便了。
刷题之——Leetcode12道简单题,通过这12道简单题,让你对Leetcode有所新的理解,增强自己的做题能力。
Consider two natural numbers A and B. Let S be the sum of all natural divisors of A^B. Determine S modulo 9901 (the rest of the division of S by 9901). Input
领取专属 10元无门槛券
手把手带您无忧上云