#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define max 32768
int cal_sqare(int n)
{
    int i;
    int j;
    int k;
    int l;
    int sum = 0;
    int count = 0;

    int s = (int)sqrt(n);

    for (i = 1; i <= s; i++)
    {
        sum += i * i;

        if(n == sum)
        {
            count++;
            sum = 0;
            break;
        }

        for (j = i; j <= s; j++)
        {
            sum += j * j;

            if (n == sum)
            {
                count++;
                sum -= j * j;
                break;
            }

            if (sum > n)
            {
                sum -= j * j;
                break;
            }

            for (k = j; k <= s; k++)
            {
                sum += k * k;

                if (n == sum)
                {
                    count++;
                    sum -= k * k;
                    break;
                }

                if (sum > n)
                {
                    sum -= k * k;
                    break;
                }

                for (l = k; l <= s; l++)
                {
                    sum += l * l;

                    if(n == sum)
                    {
                        count++;
                        sum -= l * l;
                        break;
                    }

                    if (sum > n)
                    {
                        sum -= l * l;
                        break;
                    }

                    sum -= l * l;
                }
                sum -= k * k;
            }
            sum -= j * j;
        }
        sum -= i * i;
    }

    return count;
}

int main()
{
    int i = 0;
    int j;
    int c;
    int input[255];
    char line[255];

    FILE *file;

    if((file = fopen("input.txt", "r")) == NULL)
    {
        printf("open file error!\n");
        return -1;
    }

    do
    {
        fgets(line, 255, file);
        input[i++] = atoi(line);
    }while((input[i - 1] != 0) && (i < 255));

    for (j = 0; j < (i - 1); j++)
    {
        if (input[j] <= max)
        {
            c = cal_sqare(input[j]);
            printf("%d\n", c);
        }
        else
        {
            printf("line%d's value in the file is larger than 2^15\n", j);
        }
    }
    return 0;
}

/***************************************************************************************
  运行环境：
   Microsoft Visual C++ 6.0

  程序设计思想:
    获得信息:
      rowInfo: 第i行可以放的数(如: 5) , 则 rowInfo[i][5-1] = 1
      rowSepColInfo: 第i行不可以放的数(如: 5)的列号 , 则 rowSepColInfo[i][5-1] = 列号
      colInfo, colSepRowInfo 与此类似,
    数据处理
      1. 每三行一组,在这三行中找出在同一列中，只有一个位置可以放的数，即满足
       （rowInfo[i][j] + rowInfo[i][j+1] + rowInfo[i][j+2] == 1）, 找出该元素的
        行号和列号。然后，如果在这一行的三列中，只有一个位置放数，则将该元素放到
        对应的坐标上，修改rowInfo 和 colInfo 信息。
      2. 用同样方法处理，每三列一组
      3. 对每一行剩余可以放的元素（如：5），检测从第0列到N-1列可以放的元素，如果只有一列
         可以放该元素，则在对应位置放上该元素（5），然后修改rowInfo 和 colInfo 信息
      4. 用同样的方法处理每一列
****************************************************************************************/

#include <iostream>
#include <fstream>

using namespace std;

#define N 9

int nineSquare[N][N]={{0, 0, 3, 8, 1, 0, 0, 0, 9},
                      {5, 0, 0, 4, 0, 0, 0, 8, 0},    
                      {0, 6, 0, 9, 0, 0, 1, 0, 0},
                      {0, 0, 8, 0, 3, 0, 0, 0, 6},
                      {0, 0, 0, 0, 0, 0, 0, 0, 0},
                      {9, 0, 0, 6, 0, 0, 5, 0, 0},
                      {0, 0, 6, 0, 0, 9, 0, 1, 0},
                      {0, 1, 0, 0, 0, 5, 0, 0, 4},
                      {2, 0, 0, 0, 4, 8, 7, 0, 0},
};

int rowInfo[N][N] = {0}; // 存储每一行可以放的信息
int rowSpeColInfo[N][N] = {0}; // 存储不能放数据的元素所在 N 行的列号
int colInfo[N][N] = {0}; // 存储每一列可以放的信息
int colSpeRowInfo[N][N] = {0}; // 存储不能放数据的元素所在 N 列的行号

void getInfo()
{  // 得到每行每列可以存放的信息, 1表示当前位置可以放数字

    // 初始化 rowInfo, colInfo 数组, 所有位置都能放数据
    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < N; ++j)
        {
            rowInfo[i][j] = 1;
            colInfo[i][j] = 1;
        }
    }

    for( i = 0; i < N; ++i)
    {
        for(int j = 0; j < N; ++j)
        {
            if(nineSquare[i][j] != 0)
            {
                rowInfo[i][ nineSquare[i][j]-1 ] = 0; // 当前行 对应nineSquare[i][j]-1 的位置 不能放了
                rowSpeColInfo[i][nineSquare[i][j]-1 ] = j; // 记录当前行不能放数据的 位置（i, j）
                colInfo[ nineSquare[i][j]-1 ][j] = 0; // 当前列 对应nineSquare[i][j]-1 的位置 不能放了
                colSpeRowInfo[ nineSquare[i][j]-1 ][j] = i; // 记录当前列不能放数据的 位置（i, j）
            }
        }
    }
}

// 由于空格太多，请用Vc里自动排版功能Alt+F8
bool process()
{ // 对数据数组进行处理, 如果当前有数据处理，返回true, 否则，返回false

int x, y;
int value;

bool flag = false;

getInfo();

int i , j;

for(i = 0; i < 3; ++i)
{
for( j = 0; j < N; ++j)
{
int startPos = 0; // 

// 找到每三行中一行必须存在的数
if(rowInfo[i*3][j] + rowInfo[i*3+1][j] + rowInfo[i*3+2][j] == 1)
{  //  找到三列中惟一存在的数

y = j;
value = j + 1;

if(rowInfo[i*3][j] == 1)
{
x = i*3;
}
else
startPos += rowSpeColInfo[i*3][j] / 3;

if(rowInfo[i*3+1][j] == 1)
{
x = i*3+1;
}
else
startPos += rowSpeColInfo[i*3 + 1][j] / 3;

if(rowInfo[i*3+2][j] == 1)
{
x = i*3+2;
}
else
startPos += rowSpeColInfo[i*3 + 2][j] / 3;

//cout << "by x:      x = " << x << "   y = " << y << "  value = " << value << endl;

startPos = (3 - startPos)*3;
int goodX, goodY;
int count = 0;
for(int m = startPos; m < startPos+3; ++m)
{
if(nineSquare[x][m] == 0)  // ( x, m ) 可以放元素
{
if(colInfo[j][m] == 1)  // m 列中 可以存放 value 为 j 的元素
{
goodX = x;
goodY = m;
count ++; // 计数 可以替换的位置
}
}
}

if( count == 1) // 只有一个位置被替换
{
nineSquare[goodX][goodY] = j+1;

// 修改rowInfo colInfo信息
rowInfo[goodX][j] = 0;
colInfo[j][goodY] = 0;

flag = true; // 进行了数据处理
}
}
}
}

// 对每三列的数据处理
for(j = 0; j < 3; ++j)
{
for( i = 0; i < N; ++i)
{
// 找到每三列中一行必须存在的数
if(colInfo[i][j*3] + colInfo[i][j*3+1] + colInfo[i][j*3+2] == 1)
{
int startPos = 0; // 

x = i;
value = i + 1;
if(colInfo[i][j*3] == 1)
{
y = j*3;
}
else
startPos += colSpeRowInfo[i][j*3] / 3;

if(colInfo[i][j*3+1] == 1)
{
y = j*3+1;
}
else
startPos += colSpeRowInfo[j][i*3 + 1] / 3;

if(colInfo[i][j*3+2] == 1)
{
y = j*3+2;
}
else
startPos += colSpeRowInfo[j][i*3 + 2] / 3;

//cout << "by y:      x = " << x << "   y = " << y << "  value = " << value << endl;

startPos = (3 - startPos)*3;
int goodX, goodY;
int count = 0;
for(int m = startPos; m < startPos+3; ++m)
{
if(nineSquare[m][y] == 0)  // ( x, m ) 可以放元素
{
if(rowInfo[m][j] == 1)  // m 列中 可以存放 value 为 j 的元素
{
goodX = m;
goodY = y;
count ++; // 计数 可以替换的位置
}
}
}

if( count == 1) // 只有一个位置被替换
{
nineSquare[goodX][goodY] = j+1;

// 修改rowInfo colInfo信息
rowInfo[goodX][j] = 0;
colInfo[j][goodY] = 0;

flag = true; // 进行了数据处理
}
}
}
}


// 对每一行
for(i = 0; i < N; ++i)
{
for(j = 0; j < N; ++j)
{
if( rowInfo[i][j] == 1) // 第 i 行可以放的元素 j+1
{
int count = 0; // 记录可以拥有该元素的列的次数

int goodX, goodY;

goodX = i;
for(int k = 0; k < N; ++k)
{
if( colInfo[j][k] == 1 && nineSquare[i][k] == 0) // 第k列可以拥有该元素
{
goodY = k;
count ++;
}
}

if(count == 1) // 只有一列可以放这个元素
{
nineSquare[goodX][goodY] = j+1;

// 修改rowInfo colInfo信息
rowInfo[goodX][j] = 0;
colInfo[j][goodY] = 0;

flag = true; // 修改了数据
}
}
}
}

// 对每一列
for(j = 0; j < N; ++j)
{
for(i = 0; i < N; ++i)
{
if( colInfo[i][j] == 1) // 第 j 列可以放的元素 i+1
{
int count = 0; // 记录可以拥有该元素的列的次数

int goodX, goodY;

goodY = j ;
for(int k = 0; k < N; ++k)
{
if( rowInfo[k][i] == 1 && nineSquare[k][j] == 0 ) // 第k行可以拥有该元素, 并且(k, j) 没有元素
{
goodX = k;
count ++;
}
}

if(count == 1) // 只有一列可以放这个元素
{
nineSquare[goodX][goodY] = i+1;

// 修改rowInfo colInfo信息
rowInfo[goodX][j] = 0;
colInfo[j][goodY] = 0;

flag = true; // 修改了数据
}
}
}
}

return flag;
}

void display()
{ // 显示九宫表的信息

    for(int i = 0; i < N; ++i)
    {
        for(int j = 0; j < N; ++j)
        {
            cout << nineSquare[i][j] << '\t';
        }
        cout << endl;
    }
}

int main()
{
    bool flag = true;

    while( flag ) // 调用处理函数，直到不能再放入元素为止。
        flag = process();    

    cout << "九宫表是：" << endl;
    display();

    cout << "\n管理员密码后九位是: " << endl;
    for(int i = 0; i < N; ++i)
    {
        cout << nineSquare[4][i] << '\t';
    }
    cout << endl;

    return 0;
}

// 第二题，时间来不及了，就测了25 的结果正确， 也把它交上


#include <iostream>
#include <math.h>

using namespace std;

int main()
{
int m = 25;

int n = sqrt(m);

int count = 0;

for( int a = n; a > 0; --a )
{
int b = a;
while( a*a + b*b > m && b > 0)
b--;

if( a*a + b*b == m)
{
count++;
cout << "a : " << a << "  b : " << b << endl;
b--;
}

if(b > 0)
{
// 第三个数
int c = b;
while( a*a + b*b + c*c > m && c > 0)
c--;

if( a*a + b*b + c*c == m)
{
count++;
cout << "a : " << a << "  b : " << b << endl;
c--;
}

if( c > 0 )
{
int d = c;
while( a*a + b*b + c*c + d*d > m && d > 0)
d--;

if( a*a + b*b + c*c + d*d == m)
{
cout << "a : " << a << "  b : " << b << "   d : " << d << endl;
count++;
c--;
}
}

}
}

cout << count << endl;
return 0;
}

比赛时间到, 结贴!