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