NYOJ

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

#include<stdio.h>

#include<math.h>

int 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的范围内，那么这个数就是完全平方数。下面是相关的程序：

#include<cstdio>

#include<cmath>

#include<ctime>

#include<queue>

#include<stack>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

using 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()

{

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......），那么头减尾加一就是这个数列的长度，而这个长度就是完全平方数的个数，我们只需要计算头和尾元素的数值就可以了，再也不用迭代了，这就显著的节省了计算的时间。

#include<stdio.h>

#include<math.h>

int 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了。。。。。。。

网址：NYOJ https://www.yuejiaxmz.com/news/view/230419

随便看看