NYOJ--1126--csdn第五届在线编程大赛-完全平方

NYOJ--1126--csdn第五届在线编程大赛-完全平方

看到这个题目的第一反应就是遍历A~B之间的所有数字， 然后判断这些数字是不是完全平方数， 判断这些数字是不是完全平方数的方法就是对这些数字开平方 求其平方根，获得平方根的整数部分，然后将这个整数部分再平方， 判断平方之后的结果是否是当前数字，如果这个数字不是平方数， 就不相等（因为舍弃了小数部分）。下面就是这种方法的具体C++代码：

//TimeLimitExceeded #include#includeint main(){ int n,m,i,j; while(~scanf("%d%d",&n,&m)) { int c=0; for(i=n;i<=m;i++){ int cnt=sqrt(i); int ans=(int)cnt; if(ans*ans==i) { c++; } } printf("%d\n",c); }}

但是我们发现，这种方法的效率太低，因为我们需要对[A,B]之间的所有数字都调用一次sqrt()函数，一次乘法操作，如果我们使用测试数据1 2000000000，会发现程序的执行时间相当长，我们是否可以不使用sqrt()函数，这样

的话我们就省略掉了函数调用的代价，我们可以从ceil( sqrt(numA) )（对numA求平方根然后向上取整）开始计算

i*i，判断i*i是否 < numB，如果在numB的范围内，那么这个数就是完全平方数。下面是相关的程序：

//Times:5522ms#include#include#include#include#include#include#include#include#includeusing namespace std;#define Max(a,b) a>b?a:b#define min(a,b) a>b?b:a#define Mem(a,b) memset(a,b,sizeof(a))int divs[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};int main(){ //freopen("1.txt","r",stdin); //freopen("2.txt","w",stdout); int t,i,j,k,a,b,ans; int n,m; while(~scanf("%d%d",&n,&m)) { ans=0; for(i=ceil(sqrt(n));; i++)//向上取整 { int cnt=i*i; if(cnt>=n&&cnt<=m) { ans++; } else if (cnt>m) { break; } } printf("%d\n",ans); }}

但是有没有更好的方法呢？numA到numB之间的完全平方数是这个样子的：

1 4 9 16 25 .........它们之间的距离不是1，

如果我们把这些完全平方数映射成距离为1的数列（1,2,3,4,5......），那么头减尾加一就是这个数列的长度，而这个长度就是完全平方数的个数，我们只需要计算头和尾元素的数值就可以了，再也不用迭代了，这就显著的节省了计算的时间。

//Times:60ms;#include#includeint main(){ int numA = 0; int numB = 0; while(scanf("%d %d",&numA, &numB) != EOF ) { int count = 0; count=floor(sqrt(numB))-ceil(sqrt(numA))+1; printf("%d\n",count); } return 0;}

O了。。。。。。。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。