题目描述
蓝桥小镇披萨店的老板刚刚烤制了他人生中的第 n 个披萨！为了庆祝这一重要时刻，他推出了一项名为'幸运订单'的活动，顾客有机会赢取免费披萨。以下是活动的具体规则：
- 生成订单编号：每位顾客需要生成一个九位数的订单编号。生成方法如下：首先，将数字 1 到 8 进行任意排列（每个数字正好出现一次），组成一个八位数。然后，在这个八位数的任意位置（可以是开头、结尾或中间）插入一个 1 到 8 的数字，从而得到一个九位数的订单编号。
- 计算最大公约数，赢取免费披萨：披萨店老板会计算每位顾客生成的订单编号与 n 的最大公约数（GCD）。如果某个订单编号与 n 的最大公约数最大，那么该顾客就有机会赢得免费披萨。注意：订单编号必须严格满足上述生成规则，如果有多个订单编号与 n 的最大公约数相同且达到最大值，则只有生成数值最小的订单编号的顾客能够获奖。
现在，小蓝也想参加这个活动，并希望赢取免费披萨。请你帮助小蓝找出能够让他赢得免费披萨的订单编号。
输入格式
输入一行包含一个八位的正整数 n，表示披萨店老板烤制的第 n 个披萨。
输出格式
输出一行包含一个九位的正整数表示答案，即小蓝能够赢得免费披萨的最小订单编号。
输入输出样例 #1
输入 #1
12345678
输出 #1
415637826
说明/提示
评测用例规模与约定
对于所有评测用例，$10^7 \le n < 10^8$。
题意
首先按以下规则生成一个九位数的订单编号：
- 首先，将数字 1 到 8 进行任意排列（每个数字正好出现一次），组成一个。
- 然后，在这个八位数的任意位置（可以是开头、结尾或中间）插入一个 1 到 8 的数字，从而得到一个九位数的。
接着，我们需要找到一个这样的九位数，要求与 n 的最大公约数最大且这个数尽量小。
思路
时间限制为两秒，所以考虑暴力搜索。
首先使用 DFS 生成全排列，包含所有按规则组成的八位数。
接着枚举插入的位置与数字，得到所有合法订单编号。
最后考虑是否为与 n 的最大公约数最大且最小的数即可。
代码
#include <bits/stdc++.h>
using namespace std;
long long n, max_gcd = -1, minn = INT_MAX;
int a[10], tot;
void dfs(int pos) {
if (pos == 8) {
string s = "";
for (int i = 1; i <= ; i++) {
s += (a[i] + );
}
( ins = ; ins <= ; ins++) {
( num = ; num <= ; num++) {
string nine = s.(, ins) + (num + ) + s.(ins);
val = (nine);
now_gcd = __gcd(val, n);
(now_gcd > max_gcd) {
max_gcd = now_gcd;
minn = val;
} (now_gcd == max_gcd) {
(val < minn) minn = val;
}
}
}
;
}
( i = ; i <= ; i++) {
flag = ;
( j = ; j <= pos; j++) {
(a[j] == i) {
flag = ;
;
}
}
(!flag) {
a[pos + ] = i;
(pos + );
}
}
}
{
ios::();
cin.();
cout.();
string s;
cin >> s;
n = (s);
();
cout << minn;
;
}
