LQ0009 平方十位数【枚举】

题目来源：蓝桥杯2017决赛

题目描述
由0~9这10个数字不重复、不遗漏，可以组成很多10位数字。
这其中也有很多恰好是平方数（是某个数的平方）。
比如：1026753849，就是其中最小的一个平方数。
请你找出其中最大的一个平方数是多少？

输出格式
输出一个整数表示答案

问题分析
这个题用枚举来解决，一种是枚举数，其平方为10位数，再判定是否正好覆盖数字0-9；另外一种是枚举0-9的数字构成的数，然后判定该数是否为平方数。枚举0-9数字可以使用置换函数prev_permutation()来实现。
不论哪一种枚举，都是从大到小再做判定。
这个题算出的结果是9814072356。

先求枚举的范围，数字的平方为10位数，编写以下C语言离线程序：

/* LQ0009 平方十位数 离线计算用于计算值的范围 */

#include 
#include 

char s[16];

int main()
{
    int i = 1, start, end;
    for (; ; i++) {
        sprintf(s, "%d", i * i);
        if (strlen(s) >= 10) {
            start = i;
            break;
        }
    }

    for (i++; ; i++) {
        sprintf(s, "%d", i * i);
        if (strlen(s) > 10) {
            end = i - 1;
            break;
        }
    }

    printf("%d %d\n", start, end);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

上述程序计算的结果是"31623 99999"，那么结果应该是31623到99999之间的平方数，从大到小寻找到覆盖0-9数字的数即得到结果。确定有解的话，有最大数就够了。为了保险起见，在这2个数的范围内答案。

AC的C语言程序如下：

/* LQ0009 平方十位数 */

#include 
#include 

char s[10 + 1];
int cnt[10];

int main()
{
    for (long long i = 99999; i >= 31623; i--) {
        sprintf(s, "%lld", i * i);

        memset(cnt, 0, sizeof cnt);
        for (int j = 0; s[j]; j++)
            cnt[s[j] - '0']++;

        int flag = 1;
        for (int i = 0; i < 10; i++)
            if (cnt[i] != 1) {
                flag = 0;
                break;
            }

        if (flag) {
            printf("%lld\n", i * i);
            break;
        }
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

AC的C++语言程序（枚举0-9数字）如下：

/* LQ0009 平方十位数 */

#include 
#include 
#include 
#include 

using namespace std;

bool issquare(long long n)
{
    long long t = sqrt(n);
    if (t * t == n) return true;
    else return false;
}

int main()
{
    char s[] = "9876543210";
    do {
        if (issquare(atoll(s))) {
            cout << s << endl;
            break;
        }
    } while (prev_permutation(s, s +10));

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28