solution.md

# 方程整数解

**题目描述**

方程: a^2 + b^2 + c^2 = 1000  

这个方程有正整数解吗？有：a,b,c=6,8,30 就是一组解。   

求出 a^2 + b^2 + c^2 = n(1<=n<=10000)的所有解，解要保证c>=b>=a>=1。

**输入**

存在多组测试数据，每组测试数据一行包含一个正整数n(1<=n<=10000)

**输出**

如果无解则输出"No Solution"。  

如果存在多解，每组解输出1行，输出格式：a b c，以一个空格分隔  

按照a从小到大的顺序输出，如果a相同则按照b从小到大的顺序输出，如果a,b都相同则按照c从小到大的顺序输出。

**样例输入**

```
1000
```

**样例输出**

```
6 8 30
10 18 24
```

以下程序可以实现该功能，请你计算该程序的算法复杂度：

```c
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    bool flag = false;
    while (cin >> n)
    {
        flag = false;
        for (int i = 1; i <= sqrt(n); i++)
        {
            for (int j = i; j <= sqrt(n); j++)
            {
                for (int k = j; k <= sqrt(n); k++)
                {
                    if (i * i + j * j + k * k == n)
                    {
                        cout << i << ' ' << j << ' ' << k << endl;
                        flag = true;
                    }
                    else if (i * i + j * j + k * k > n)
                        break;
                }
            }
        }
        if (!flag)
            cout << "No Solution" << endl;
    }

    return 0;
}
```

## 答案

```c
O(n^1.5)
```
## 选项


### A

```c
O(n^3)
```

### B

```c
O(n^2)
```

### C

```c
O(n^2.5)
```