这个long long究竟放在哪里,为什么我改了x的类型还是超时
这个估计你不能循环从1开始进行判断,可以考虑用二分法折半查找。比如在1到x/2之间进行折半比较,判断平方数与n的关系,直到遇到相等数,或者比n大的和比n小的数之差是1则结束
#include <stdio.h>
#include <stdlib.h>
int main()
{
long long x,l,h,left,right,mid;
int n,i;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%lld",&x);
left = 1;
right = x/2;
h = right;
l = left;
while(left < right)
{
mid = (left + right)/2;
if(mid * mid == x)
{
printf("%lld * %lld = %lld\n",mid,mid,mid*mid);
break;
}
else if(mid * mid < x)
{
if(mid == h-1)
{
printf("%lld * %lld = %lld\n",mid,mid,mid*mid);
break;
}
left = mid;
l = left;
}
else
{
if(mid == l+1)
{
printf("%lld * %lld = %lld\n",l,l,l*l);
break;
}
right = mid;
h = right;
}
}
}
}
可以使用迭代算法计算平方根(参考https://en.wikipedia.org/wiki/Square_root#Computation
迭代公式是
#include <iostream>
unsigned long long my_sqrt(unsigned long long x) {
if (x == 0)
return 0;
if (x == 1)
return 1;
unsigned long long x_n = x / 2;
while (1) {
unsigned long long x_n1 = (x_n + x / x_n) / 2;
if (x_n1 >= x_n)
break;
x_n = x_n1;
}
return x_n;
}
int main() {
unsigned long long x;
while (std::cin >> x)
std::cout << my_sqrt(x) << '\n';
return 0;
}