526互联

C++ 判断一个数是不是完全平方数

发布时间 2024-01-07 23:09:20作者: BadBadBad__AK

1、利用平方数的性质：

1=1，4=1+3，9=1+3+5，16=1+3+5+7以此类推，模仿它可以使用一个while循环，不断减去一个从1开始不断增大的奇数，若最终减成了0，说明是完全平方数，否则，不是。
时间复杂度\(O(n)\)

bool isPerfectSquare(int num) 
{
    int num1 = 1;
    while(num > 0) 
    {
        num -= num1;
        num1 += 2;
    }
    return num == 0;
}

2、二分法查找

速度比第一种要快上不少
时间复杂度:\(O(\log n)\)

bool isPerfectSquare(int num)
{
    if(num == 1)
        return true;
 
    int start = 2;
    int end = num;
    int mid;
    while(start <= end)
    {
        mid = start + (end - start)/2;
        if(mid == num / mid && num % mid == 0)
            return true;
 
        if(mid > num / mid)
            end = mid - 1;
        else
            start = mid + 1;
    }
    return false;
}

例题

Codeforces:Can I Square?

Code

#include <bits/stdc++.h>
using namespace std;
bool isPerfectSquare(long long num)
{
	if(num == 1)
		return true;
	
	long long start = 2;
	long long end = num;
	long long mid;
	while(start <= end)
	{
		mid = start + (end - start)/2;
		if(mid == num / mid && num % mid == 0)
			return true;
		
		if(mid > num / mid)
			end = mid - 1;
		else
			start = mid + 1;
	}
	
	return false;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		long long a,b;
		cin>>a;
		long long sum=0;
		for(int j=1;j<=a;j++)//总和加起来
		{
			cin>>b;
			sum+=b;
		}
		if(isPerfectSquare(sum))//判断是否为平方数
		{
			cout<<"YES"<<endl;
		}
		else
		{
			cout<<"NO"<<endl;
		}
	}
	
	
	return 0;
}