题目描述题目要求找出所有满足条件的整数对(s1,s2)(s_1, s_2)(s1​,s2​)使得s1/s2Ns_1 / s_2 Ns1​/s2​N其中NNN是给定的整数s1s_1s1​和s2s_2s2​的十进制表示中均不包含重复数字。输出时按s1s_1s1​升序排列。输入格式第一行一个整数TTT表示测试用例的数量后面跟一个空行。每个测试用例一行包含一个整数NNN。两个连续测试用例之间由一个空行分隔。输出格式对于每个测试用例输出若干行每行格式为s1 / s2 N。按s1s_1s1​升序排列。两个连续测试用例的输出之间由一个空行分隔。样例输入1 1234567890输出1234567890 / 1 1234567890 2469135780 / 2 1234567890 4938271560 / 4 1234567890 6172839450 / 5 1234567890 8641975230 / 7 1234567890 9876543120 / 8 1234567890题目分析本题的核心是枚举所有满足条件的s2s_2s2​然后计算s1N×s2s_1 N \times s_2s1​N×s2​并检查s1s_1s1​和s2s_2s2​是否都不含重复数字。枚举范围s2s_2s2​必须是各位数字不重复的正整数且s1s_1s1​也必须是各位数字不重复的正整数。由于s1s_1s1​最大可能为987654321098765432109876543210101010位数字含000到999各一次因此s2≤9876543210/Ns_2 \le 9876543210 / Ns2​≤9876543210/N。但更简单的方法是预先生成所有各位数字不重复的数字最多为∑k110P(10,k)≈9,864,100\sum_{k1}^{10} P(10, k) \approx 9,864,100∑k110​P(10,k)≈9,864,100但实际有效数字不含前导零约为∑k1109×P(9,k−1)≈9,864,100\sum_{k1}^{10} 9 \times P(9, k-1) \approx 9,864,100∑k110​9×P(9,k−1)≈9,864,100仍然太大。需要优化。实际上由于s1s_1s1​和s2s_2s2​都不含重复数字且s1N×s2s_1 N \times s_2s1​N×s2​s2s_2s2​的位数不能太大。通常枚举s2s_2s2​到10610^6106左右即可。参考代码中预先生成了所有位数不超过666且各位数字不重复的数字包括前导零实际生成的是不含前导零的共约99×99×9×8…9 9 \times 9 9 \times 9 \times 8 \ldots99×99×9×8…数量约9×∑k05P(9,k)≈9×(1972504302415120)9×187301685709 \times \sum_{k0}^{5} P(9, k) \approx 9 \times (1 9 72 504 3024 15120) 9 \times 18730 1685709×∑k05​P(9,k)≈9×(1972504302415120)9×18730168570加上000共约171717万完全可接受。生成方法使用回溯法生成所有各位数字不重复的数字允许000到999但不能有前导零参考代码中从111到999开始然后递归添加000到999中未使用的数字生成的数字包括000本身吗初始current0但第一层循环从000开始会生成以000开头的数字如0、01即111、02等。但0作为s2s_2s2​会导致s10s_10s1​0不符合要求s1s_1s1​应无重复数字000有重复000只有一位数字不算重复。实际实现中生成的数字包括000但后续检查时会过滤。检查重复数字对s1s_1s1​和s2s_2s2​的十进制字符串分别检查是否有重复字符排序后相邻比较即可。复杂度分析预生成约171717万个数每个测试用例遍历这些数直到N×s29876543210N \times s_2 9876543210N×s2​9876543210实际枚举次数有限。代码实现// Magic Numbers// UVa ID: 471// Verdict: Accepted// Submission Date: 2016-07-18// UVa Run Time: 0.020s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;vectorlonglongnumbers(200000,0);vectorboolvisited(10);intcounter0;voidbacktrack(longlongcurrent,intdepth){if(depth6)return;for(inti0;ivisited.size();i)if(visited[i]false){visited[i]true;numbers[counter]current*10i;backtrack(current*10i,depth1);visited[i]false;}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);fill(visited.begin(),visited.end(),false);backtrack(0,0);sort(numbers.begin(),numbers.end());counterunique(numbers.begin(),numbers.end())-numbers.begin();intcases;cincases;longlongn;for(inti1;icases;i){if(i1)coutendl;cinn;for(intj1;jcounter;j){longlongmultiplicationn*numbers[j];if(multiplication9876543210LL){string textto_string(multiplication);sort(text.begin(),text.end());boolsamefalse;for(intk0;ktext.length()-1;k)if(text[k]text[k1]){sametrue;break;}if(samefalse)coutmultiplication / numbers[j] n\n;}elsebreak;}}return0;}