---
title: 7C 完美平方數
tags: solution
---

# C. 完美平方數

#include <iostream>
#include <math.h>
using namespace std;

int numSquares(int n);

int main()
{
    int num, ans;
    while (cin>>num){
        ans = numSquares(num);
        cout << ans << endl;
    } // while
}

int numSquares(int n)
{
    while (n % 4 == 0)
        n /= 4;
    if (n % 8 == 7)
        return 4;
    for (int a = 0; a * a <= n; ++a)
    {
        int b = sqrt(n - a * a);
        if (a * a + b * b == n)
        {
            return !!a + !!b;
        }
    }
    return 3;
}