【HDU/POJ/ZOJ】Calling Extraterrestrial Intelligence Again （素数打表模板）
http://poj.org/problem?id=1411 POJ
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1689 ZOJ
http://acm.hdu.edu.cn/showproblem.php?pid=1239 HDU
都是同一个题，但是可能你在HDU上AC，在POJ和ZOJ上是TLE（所以还有待改进）
【题目大意】In other words, you will receive an integer m and a fraction a / b. It holds that m > 4 and 0 < a / b < 1. You should find the pair of prime numbers p, q such that pq <= m and a / b <= p / q <= 1, and furthermore, the product pq takes the maximum value among such pairs of two prime numbers. You should report p and q as the "most suitable" width and height of the translated picture.
You may assume 4 < m <= 100000 and 1 <= a <= b <= 1000.
素数打表 + 遍历 + 剪枝
【注意】
prime数组里需要存放素数的最大值是多少，存的过多也会TLE。
考虑如果q是大于10000的某一个数，p是另一个质数
如果p<10，那么p/q<=0.001
如果p>10，那么pq>100000，
因为这是题目中所给条件，1 <= a <= b <= 1000，所以min（a/b）=0.001，同时要求pq <= 100000 ，所以表里的最大质数不会超过10000。
HDUAC
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;bool vis[10000];
int prime[2000];
int num = 0;
void table()
{int i,j;memset(prime,0,sizeof(prime));memset(vis,true,sizeof(vis));for(i=2;i<10000;i++){if(vis[i]){prime[num++] = i;}for(j=0;(j<num && i*prime[j]<10000);j++){vis[i*prime[j]] = false;if(i%prime[j]==0) break;}}
}int main ()
{table();int n,i,j;double a,b;
// cout << prime[num-1] << endl;while(scanf("%d%lf%lf",&n,&a,&b)!=EOF){if(n==0 && a==0 && b==0)break;double lim = a/b;int maxn = 0; int a1,a2;for(i=num-1;i>=0;i--){for(j=i;j>=0;j--){if(prime[i]>n || prime[j]>n || prime[i]*prime[j]>n || 1.0*prime[j]/prime[i]<lim)continue;if(prime[i]*prime[j]>maxn){maxn = prime[i]*prime[j];a1 = prime[i];a2 = prime[j];}}} if(a1 > a2){int t = a1;a1 = a2;a2 = t;}cout << a1 << " " << a2 << endl;}return 0;
} ALL_AC
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 10000;
bool vis[10000];
int prime[2000];
int num = 0;void table()
{int i,j;memset(prime,0,sizeof(prime));memset(vis,true,sizeof(vis));for(i=2;i<10000;i++){if(vis[i]){prime[num++] = i;}for(j=0;(j<num && i*prime[j]<10000);j++){vis[i*prime[j]] = false;if(i%prime[j]==0) break;}}
}int main ()
{table();int n,i,j;int a,b;while(scanf("%d%d%d",&n,&a,&b)!=EOF){if(n==0 && a==0 && b==0)break;double lim = 1.0*a/b;int maxn = 0; int a1,a2;for(i=num-1;i>=0;i--){if(prime[i]>n)continue;for(j=i;j<=num-1;j++)//j是比i大的素数 {int t = prime[i]*prime[j];if (prime[j]>n || t>n || 1.0*prime[i]/prime[j]<lim)break;if(t>maxn){maxn = t;a1 = prime[i];a2 = prime[j];}}} cout << a1 << " " << a2 << endl;}return 0;
} #include<iostream>
#include<cstring>
#include<cstdio>
#include<ctime>
#include<algorithm>
using namespace std;
#define M 1000000
bool visit[10100000];
int prime[10000000];void table1()
{memset(visit,true,sizeof(visit));int num = 0;for (int i = 2; i <= M; ++i){if (visit[i] == true){num++;prime[num] = i;}for (int j = 1; ((j <= num) && (i * prime[j] <= M)); ++j){visit[i * prime[j]] = false;if (i % prime[j] == 0) break; //点睛之笔}}
}void table2()
{memset(visit,true,sizeof(visit));int num = 0;for (int i = 2; i <= M; ++i){if(visit[i]){prime[num++] = i;for(int j=i+i;j<M;j+=i){visit[j] = false;}}}
}int main()
{clock_t start, finish; double Total_time;memset(prime, 0, sizeof(prime));int count = 0;start = clock();//开始时间 table2();finish = clock();Total_time = (double)(finish - start) / CLOCKS_PER_SEC; cout << "素数打表耗时：" << Total_time << endl; for(int i = 0; i <= M; ++i){if(prime[i]){count++;} } cout<< "在" << M << "个数中，素数个数为："<< count << endl;
}在M=1000000时，二者时间貌似差不多...
该题用这两种打表方法都可以
相关文章：
[AVR]使用AVR单片机驱动舵机
最近参加了三系举办的小车比赛(好像叫什么"驭远杯")。领导要求我驱动3-4个舵机。研究了几日，总算折腾出一个方案..、 1.舵机驱动的基本原理 （可以参考http://blog.sina.com.cn/s/blog_8240cbef01018hu1.html） "控制信号由接收…
高阶函数的使用
问题 字节跳动面试时问题：原函数例如fetchData是一个异步函数，尝试从服务器端获取一些信息并返回一个Promise。写一个新的函数可以自动重试一定次数，并且在使用上和原函数没有区别。 思路 这个问题其实不是很难，不过可能是太菜了紧…
内存溢出和内存泄漏的定义，产生原因以及解决方法（面试经验总结）
一、定义（概念与区别） 内存溢出 out of memory，是指程序在申请内存时，没有足够的内存空间供其使用，出现out of memory；比如申请 了一个integer,但给它存了long才能存下的数，那就是内存溢出。 …
【Codeforces】716B Complete the Word （26个字母）
http://codeforces.com/contest/716/problem/B 给你一个字符串该字符串中是否存在长度为26且这26个字母没有重复 一个满足上述条件但是部分区域是问号的话，需要用剩下的字母覆盖掉问号，其余部分的问号可以随便赋值 没有的话输出-1 暴力即可。 #incl…
MySQL ERROR 1878 解决办法
MySQL ERROR 1878报错解决办法错误重现Part1:大表修改字段mysql> ALTER TABLE erp-> ADD COLUMN eas_status tinyint(3) unsigned NOT NULL DEFAULT 0 AFTER totalprice;ERROR 1878 (HY000): Temporary file write failure.mysql> \q这里可以看到，添加字…
共享程序集和强命名程序集（3）：强命名程序集的一些作用
强命名程序集能防篡改 用私钥对程序集进行签名，并将公钥和签名嵌入程序集，CLR就可以炎症程序集未被修改或破坏。程序集安装到GAC时，系统对包含清单的那个文件的内容进行哈希处理，将Hash值与PE文件中嵌入的RSA数字签名进行比较。如…
堆和栈的区别（面试经验总结）
C中，内存分为5个区：堆、栈、自由存储区、全局/静态存储区和常量存储区。 栈：是由编译器在需要时自动分配，不需要时自动清除的变量存储区。通常存放局部变量、函数参数等。 堆：是由new分配的内存块，由程序员…
百度Q3财报里的“大生意”
在今日发布的Q3财报中，百度花了不少篇幅来介绍人工智能业务的进展，作为百度的技术核心，近段时间几乎所有百度业务都在与人工智能做深入结合，这预示着移动互联网信息化技术发展已经全面开启人工智能时代，而百度势必要在…
【Codeforces/HDU】76A Plus and xor / 2095 find your present (2)（异或）。
http://codeforces.com/contest/76/problem/D A X Y B X xor Y 异或（不进位加法）：两个二进制数，对应的位置上，相同为0，不同为1 性质：a^a0，a^0a，满足交换律 所以…
前端项目如何管理
前端项目如何管理 前端项目的管理分为两个维度：项目内的管理与多项目之间的管理。 1. 项目内的管理 在一个项目内，当有多个开发者一起协作开发时，或者功能越来越多、项目越来越庞大时，保证项目井然有序的进行是相当重要的。 一般会…
CMake学习（一）
什么是 CMake 你或许听过好几种 Make 工具，例如 GNU Make ，QT 的 qmake ，微软的 MS nmake，BSD Make（pmake），Makepp，等等。这些 Make 工具遵循着不同的规范和标准，所执行…
【Codeforces】1104C Grid game （变异的俄罗斯方块）
http://codeforces.com/problemset/problem/1104/C 4 X 4 的方格 放置 1*2的矩形（用1表示）和2*1的矩形（用0表示） 只要有一行或者一列都填满了，就会自动消除，就可以放心的矩形了，只要不重叠就可…
如何创建.gitignore文件，忽略git不必要提交的文件
1、在需要创建 .gitignore 文件的文件夹, 右键选择Git Bash 进入命令行，进入项目所在目录。 2、输入 touch .gitignore ，生成“.gitignore”文件。 3、在”.gitignore” 文件里输入你要忽略的文件夹及其文件就可以了。（注意格式） …
软件安全访谈：ZipSlip、NodeJS安全性和BBS攻击
正如Nodejs Security WG成员和Snyk开发者布道师Liran Tal所写的那样，自BBS早期以来，这种漏洞利用的矢量攻击已经为人所知。InfoQ采访了Tal，了解了更多有关软件安全性（尤其是Nodejs安全性）的相关信息。今年早些时候&…
客户端与服务器的数据交互
毕设需要接粗到一些关于app和前端后端的东西，学习记录一下。 首先不要管安卓端还是苹果端，现在一般都是响应式的app，放到安卓或者苹果或者pc或者平板都是没有问题的。一般采用的是http接口通讯，或者socket连接。具体你要去查资料…
【Codeforces】908B New Year and Buggy Bot（暴力+全排列）
http://codeforces.com/contest/908/problem/B 0 1 2 3 可以对应 上下左右。（具体哪个对应哪个，试过才知道） str 的 长度 为 100，0 1 2 3 的全排列一共24种，最坏的情况可以看成遍历长为2400的字符串，不会…
swoole实现数据库连接池
2019独角兽企业重金招聘Python工程师标准>>> 原生 PHP CURD 让我们来回顾一下PHP中数据库的使用 <?php # curd.php$id 1;$dbh new PDO(); $stmt $dbh->prepare(SELECT * FROM user WHERE id:id); $stmt ->bindValue(:id, $id); $user $stmt->f…
bats-Bash自动化测试工具
本文分析了bats--Bash自动化测试工具的安装、语法、常用指令及常用函数等内容。上篇文章回顾：学习RAID 01/10/10E的区别bats 是一个符合 TAP 标准 的 Bash 版测试框架，它使用了一种极为简便的方法来验证命令行程序是否正常运行。bats 要求 Bash 的最低版…
ORB + OPENCV
一、介绍 假如有两张人物图片，我们的目标是要确认这两张图片中的人物是否是同一个人。如果人来判断，这太简单了。但是让计算机来完成这个功能就困难重重。一种可行的方法是： 分别找出两张图片中的特征点描述这些特征点的属性，比较…
【Codeforces】967C Stairs and Elevators （二分）。
http://codeforces.com/contest/967/problem/C 从一个地方到另一个地方，可以选择爬楼梯或者坐电梯 ，前提是楼梯或者电梯存在。 n 楼层数 m 每一层的房间数 s 楼梯的数量 e 电梯的数量 v 电梯的速度 第2行是s个楼梯的位置 第3行是e个电梯的位置 …
webpack 最简打包结果分析
原文链接：https://ssshooter.com/2019-02... 现在的 webpack 不再是入门噩梦,过去 webpack 最让人心塞的莫过于配置文件，而 webpack4 诞生随之而来的是无配置 webpack。 使用 webpack4，至少只需要安装 webpack 和 webpack cli。所以大家完全可…
orb-slam2(学习笔记)+相机
单目（Monocular）、双目（Stereo）、深度相机（RGB-D） 深度相机能够读取每个像素离相机的距离 ，单目相机 只使用一个摄像头进行SLAM的做法叫做单目SLAM（Monocular SLAM）,结构…
如何在nuget上传自己的包+搭建自己公司的NuGet服务器（新方法）
运维相关：http://www.cnblogs.com/dunitian/p/4822808.html#iis 先注册一个nuget账号https://www.nuget.org/ 下载并安装一下NuGetPackageExplorer：https://github.com/NuGetPackageExplorer/NuGetPackageExplorer 创建一个包（vs其实也是可以…
【Codeforces】1080C Masha and two friends （棋盘染色）
http://codeforces.com/problemset/problem/1080/C 给定一个棋盘，（1，1）的位置是白色，观察可以知道，如果横纵坐标之和是偶数，那么是白色，奇数的话就是黑色。 只要算出染色以后白色方…
Java多线程001——一图读懂线程与进程
本博客 猫叔的博客，转载请申明出处前言 本系列将由浅入深，学习Java并发多线程。 一图读懂线程与进程 1、一个进程可以包含一个或多个线程。（其实你经常听到“多线程”，没有听过“多进程”嘛）2、进程存在堆和方法区 3、…
TermCriteria模板类
学习写vo过程中遇到的 类功能：模板类，作为迭代算法的终止条件。 构造函数： TermCriteria(int type,int maxCount,double epsilon); 参数说明： type 迭代终止条件类型 typeTermCriteria::MAX_ITER/TermCrite…
SQL优化快速入门
最近遇到一个专门进行SQL技术优化的项目，对很多既有的老存储过程进行调优（现在已经不再新增任何存储过程），因此系统的对SQL语句编写进行一次科学的学习变得很有必要。这儿将基于黄德承大神的Oracle SQL语句优化一书，选…
【HDU】4509 湫湫系列故事——减肥记II （区间覆盖 暴力）
http://acm.hdu.edu.cn/showproblem.php?pid4509 给出的时间段是被占用的时间，24h 1440 min，求出这些区间以外的区间长度 把00：00 - 23：59 变成0-1440 1-5都是被占用的区域，暴力很好理解 #include <iostream>…
Java并发编程71道面试题及答案
Java并发编程71道面试题及答案 1、在java中守护线程和本地线程区别？ java中的线程分为两种：守护线程（Daemon）和用户线程（User）。 任何线程都可以设置为守护线程和用户线程，通过方法Thread.setDa…
ＵＳＢ获取图像实时处理
手写ＶＯ的准备工作，调用ＵＡＢ或者本地相机获取视频图像，读取并保存视频。 #include "opencv2/core/core.hpp" #include "opencv2/highgui/highgui.hpp" #include "openc…