* on (CF-237C)*前缀和*二分查找 莫名眼熟的题目 。。这个类型的题好像有很多 。数据很大,枚举超时,又是用前缀和,我又没想到!!还要用二分,找最小的区间,然后循环这个大小的区间和,看看是否满足条件 。难点,二分前缀和 。
*处女座的测验(一) 积性函数!本身是因子,并且求出两者相乘数的因子个数 。哦嚯,素数打表,t()是积性函数,满足t(xy)=t(x)t(y),要满足最后结果>10 。对于任意一个质数来说它的因子数都是只有两个1和它本身,那么两个质数相乘就是有4个,那么再让这两个质数相乘的积再相乘的话,就会一共有16个因子,所以任意的四个质数相乘的结果的因子个数都是16个,所以根据这个条件我们先筛除前4000个质数,然后首尾两两相乘就可以得到需要的2000个数了(如果不是首尾相乘而是相邻两个相乘,到后面会超过题目要求的范围) 。
积性函数:成立需要满足:xy两两互质 。
看了两个大佬的博客,终于看了这20多个素数的题目,总的来说,素数整体题目偏简单,但是要是组合着别的算法考也不是很好理解 。难点在于->超时、题目理解、算法结合 。
要讨论判断一个【1,2^31】内的数是否为素数,因为2^31太大无法打完整的表,所以我们要投巧 。
根据基本素数判别法 。打一个1~50 000的素数表,看该数字是否存在一个1~50 000的素因子,如果存在就不是素数,否则是素数 。因为任何一个非素数都可以表示为若干个素数之积 。
#define N 50001bool isprime[N];int prime[N],nprime;//1~5万素数打表void doprime(){long long i,j;nprime=0;for(i=0;i
*POJ 2689 Prime
题意:给定两个数L,R(1≤L<R≤2 147 483 647),在[L,R]内找出相邻素数C1,C2使其距离最小,找出相邻素数C3,C4使其距离最大 。若距离相同,选最初的一组 。(R-L
思路:L和R的范围比较大,不能直接打表 。
因为正整数N是素数,当且仅当N不能被任何一个小于sqrt(N)的素数整除 。所以如果N是一个合数,那么N必然存在一个小于sqrt(N)的素数因子 。
而sqrt(2 147 483 647)
代码:(啊哈~总感觉间过好几次这个题了,可四现在才有点会,过几天可能就不能想起来这个代码了 。。但是果然吧!以前不会的早晚我都会会的!!心情不好看不进去当然是不会的啦)
#include
*算法
1.题目:判断一个【1,2^63】内的数是否为素数
2.思路:大数判断素数,这个方法大概是那种判断成功概率极大的算法,但也不是百分白的正确率的,大数的算法永远是人们心中的痛
- 年度吃羊肉总结,内含地理标志羊肉盘点以及10款好吃羊肉推荐 中国十大羊肉品牌
- 吴恩达ML简略总结
- 无矛盾的最佳球队
- 【笔试题目整理】小红书2019年校园招聘数据分析岗位在线笔试第二批
- 模拟 超大型 LED 显示屏
- 北大学霸总结高中历史:必修1-3必背知识点总结大全 历史必修三之最
- 【笔试题目整理】小红书2019年校园招聘数据分析岗位在线笔试第一批
- 议论文题目,有什么好的议论文题目
- 争了13年,如今《永恒之塔》想用怀旧服打败《魔兽》,能行吗? 中国之最课后总结
- Win10 安装Rational_Rose_2007 问题总结及解决方案