Problem J. 排列与合数

小 A 在 2023 年河南省 CCPC 大学生程序设计竞赛的赛场上遇到了一道名为 “排列与质数” 的题目。

与大多数选手一样，小 A 并没能在赛场上解决这个棘手的题目。比赛结束后，小 A 想到了一个与之相关的题目：排列与合数，可是小 A 仍然没有能力解决。这个名为 “排列与合数” 的题目是这样的：

给定一个有且仅有 5 位，且各个数位互不相同的十进制正整数 n。你可以重新排列 n 的各个数位，但需要保证重新排列得到的整数 n′ 没有前导零。请问重新排列数位得到的 n′ 能否为合数？若能为合数，请求出一个满足条件的 n′。

例如，当 n = 12345 时，任意排列得到的 n′ 均是合数，因此可以任意取 n′。当 n = 13579 时，可以重新排列数位得到合数 n′ = 97531 = 7 × 13933。

一个正整数是合数，当且仅当它可以分解为两个不小于 2 的整数的乘积。

现在，小 A 带着他的题目来到赛场上求助。你能帮助小 A 解决这个题目吗？

输入格式

本. 题. 测. 试. 点. 包. 含. 多. 组. 数. 据。.

第一行，一个正整数 T（1 ≤ T ≤ 10⁵），表示数据组数。

对于每组数据：

一行，一个正整数 n（10⁴ ≤ n < 10⁵），保证 n 的各个数位互不相同。

输出格式

对于每组数据：

输出一行，一个整数。若能重新排列 n 的数位得到合数 n′ 则输出 n′，否则输出 −1。

样例

提示

样例即是题目描述中给出的例子。

题解

官方题解：

我们比赛时注意到，由于输入是5位数，且各个位上的数字不重复，所以当所有位上的数字都是奇数时，也就只能是1,3,5,7,9的排列。题目只要求输出任一结果，所以直接输出样例中的“97531”即可。

当有位上是偶数时，只要把这个偶数放到个位，即可保证该数是合数（因为对于任何不是2的正整数，所有的偶数都是合数）。起初我们是从高位往低位检查，如果遇到偶数，则直接与个位互换。但这里遇到了一个问题：如果最高位就是偶数，而个位是0，互换之后就会出现前导零，所以在这里WA了一发。于是调整为从地位往高位检查。当数据量足够大时，从前开始和从后开始查找的效率可以说是没有差别的。

代码实现

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long

int main()
{
    int n;
    cin >> n;

    while (n--) {
        string s;
        cin >> s;
        int i = 4;
        for (; i >= 0; i--) {
            if (!((s[i] - '0') & 1)) {
                char tmp = s[i];
                s[i] = s[4];
                s[4] = tmp;
                break;
            }
        }
        if (i >= 0) {
            cout << s << endl;
        } else {
            cout << 97531 << endl;
        }
    }

    return 0;
}