★ FEATURED ARTICLE 题目描述一个双部数bipartite number\texttt{bipartite number}bipartite number是恰好由两种不同十进制数字sss和ttt组成的正整数其中sss不为000且所有sss都出现在所有ttt之前。例如444441144444114444411、414141、100000001000000010000000、555555655555565555556都是双部数而444411444441144444114和444444444444444不是。双部数可以用四个整数mmm、sss、nnn、ttt描述sss是前导数字ttt是尾随数字mmm是sss出现的次数nnn是ttt出现的次数。给定一个公钥正整数要求找到大于等于该公钥且是公钥倍数的最小双部数并输出其四元组描述。输入格式输入包含多组测试数据。每行一个正整数表示公钥范围在111到999999999999999之间。输入以单独一行的000结束。输出格式对每组测试数据输出一行格式为公钥: m s n t其中mmm、sss、nnn、ttt为描述该双部数的四个整数。样例输入125 17502 2005 0样例输出125: 1 5 2 0 17502: 4 7 4 8 2005: 3 2 3 5题目分析本题要求找到最小的双部数它是给定公钥NNN的倍数且不小于NNN。双部数由前导数字sss1≤s≤91 \le s \le 91≤s≤9、尾随数字ttt0≤t≤90 \le t \le 90≤t≤9t≠st \ne sts、前导数字个数mmmm≥1m \ge 1m≥1和尾随数字个数nnnn≥1n \ge 1n≥1确定其数值为前mmm个sss后接nnn个ttt组成的十进制数。由于N≤99999N \le 99999N≤99999双部数的位数不会太大。可以从小到大枚举双部数的总位数dmnd m ndmn对于每个位数枚举所有可能的mmm1≤md1 \le m d1≤md、sss1≤s≤91 \le s \le 91≤s≤9、ttt0≤t≤90 \le t \le 90≤t≤9t≠st \ne sts计算该双部数对NNN取模的结果若模为000且数值大于等于NNN则记录候选方案。在所有候选方案中按双部数的数值从小到大选择若数值相同则按题目定义的比较规则先按位数再按sss再按mmm最后按ttt选择。实际上由于枚举顺序按位数递增第一个找到的合法方案即为最小双部数。但需要注意对于同一总位数不同mmm、sss、ttt组合对应的双部数大小不同代码中通过自定义比较运算符operator来确保选出最小的双部数。为了快速计算双部数对NNN的模预先计算两个数组modulo1[i]表示由iii个111组成的数对NNN取模的结果modulo10[i]表示10i10^i10i对NNN取模的结果。则双部数ss⋯s⏟mtt⋯t⏟n\underbrace{ss\cdots s}_{m}\underbrace{tt\cdots t}_{n}mss⋯sntt⋯t对NNN取模的结果为(modulo1[m]×modulo10[n]×smodulo1[n]×t) mod N (\textit{modulo1}[m] \times \textit{modulo10}[n] \times s \textit{modulo1}[n] \times t) \bmod N(modulo1[m]×modulo10[n]×smodulo1[n]×t)modN若该值为000则说明该双部数是NNN的倍数。为了避免无限枚举代码中使用了剪枝策略当NNN的个位不为000时尾随数字ttt只能为000才可能使双部数被NNN整除因为若t≠0t \ne 0t0则双部数的个位为ttt而NNN的个位不为000无法整除当NNN的个位为000时ttt可以为000但需要更多位数来调整。代码中通过条件((number % 10 || d 20) ? 1 : d - 20)限制mmm的起始值避免不必要的枚举。此外还通过bigger函数检查双部数是否不小于NNN。时间复杂度最坏情况下需要枚举的位数ddd不会太大对于N≤99999N \le 99999N≤99999双部数的位数通常不超过202020左右。对于每个ddd枚举mmm、sss、ttt的组合数为O(d×9×10)O(d \times 9 \times 10)O(d×9×10)。预先计算模数组的时间为O(MAXL)O(MAXL)O(MAXL)其中MAXL10000MAXL 10000MAXL10000。整体运行时间在题目约束下可以接受。解题思路步骤1\texttt{1}1. 读取公钥NNN若N0N 0N0则结束。步骤2\texttt{2}2. 调用precalculate(N)预先计算modulo1和modulo10数组长度为MAXL。步骤3\texttt{3}3. 初始化最优解pk为一个无效的大值例如mMAXLm MAXLmMAXL。步骤4\texttt{4}4. 从总位数d2d 2d2开始递增枚举。对于每个ddd枚举前导数字个数mmm1≤md1 \le m d1≤md前导数字sss1≤s≤91 \le s \le 91≤s≤9尾随数字ttt0≤t≤90 \le t \le 90≤t≤9t≠st \ne sts。步骤5\texttt{5}5. 计算该双部数对NNN的模r(modulo1[m]×modulo10[d−m]×smodulo1[d−m]×t) mod N r (\textit{modulo1}[m] \times \textit{modulo10}[d-m] \times s \textit{modulo1}[d-m] \times t) \bmod Nr(modulo1[m]×modulo10[d−m]×smodulo1[d−m]×t)modN若r0r 0r0且通过bigger函数确认该双部数不小于NNN则生成候选candiate若它比当前最优解pk更小按自定义比较规则则更新pk。步骤6\texttt{6}6. 若当前ddd枚举完毕后pk.m MAXL说明已找到合法解跳出循环。步骤7\texttt{7}7. 输出N: pk.m pk.s pk.n pk.t。代码实现// Bipartite Numbers// UVa ID: 1051// Verdict: Accepted// Submission Date: 2018-01-18// UVa Run Time: 0.260s//// 版权所有C2018邱秋。metaphysis # yeah dot net//// Please refer to: https://github.com/morris821028/UVa/blob/master/volume010/1051%20-%20Bipartite%20Numbers%5Bbfs2%5D.cpp#includebits/stdc.husingnamespacestd;structprivateKey{intm,n,s,t;privateKey(intm0,intn0,ints0,intt0):m(m),n(n),s(s),t(t){}booloperator(constprivateKeypk)const{if(mn!pk.mpk.n)returnmnpk.mpk.n;if(s!pk.s)returnspk.s;if(m!pk.m)returnspk.t;returntpk.t;}};constintMAXL10000;intmodulo1[MAXL],modulo10[MAXL];voidprecalculate(intn){modulo1[0]0;modulo10[0]1;for(inti1;iMAXL;i){modulo1[i](modulo1[i-1]*101)%n;modulo10[i](modulo10[i-1]*10)%n;}}inlineboolbigger(intd,intm,ints,intt,intnumber){if(d6)returntrue;intr0;for(inti1;id;i)rr*10(im?s:t);returnrnumber;}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intnumber;while(cinnumber,number0){precalculate(number);privateKeypk(MAXL);for(intd2;;d){// Prune, or TLE!for(intm((number%10||d20)?1:d-20);md;m)for(ints1;s9;s)for(intt0;t9;t){if(st)continue;longlongr((longlong)modulo1[m]*modulo10[d-m]*smodulo1[d-m]*t)%number;privateKeycandiate(m,d-m,s,t);if(r0bigger(d,m,s,t,number)candiatepk)pkcandiate;}if(pk.mMAXL)break;}coutnumber: pk.m pk.s pk.n pk.t\n;}return0;}总结本题的核心是寻找大于等于给定公钥且是其倍数的最小双部数。通过枚举双部数的总位数、前导数字个数、前导数字和尾随数字利用模运算快速判断是否为公钥的倍数。预先计算由111组成的数对公钥取模的结果以及101010的幂对公钥取模的结果可以O(1)O(1)O(1)计算任意双部数的模。通过自定义比较规则确保选出最小的双部数。剪枝策略避免了不必要的枚举使得算法在题目约束下高效运行。最终输出双部数的四元组描述。
阅读完成 · 觉得有帮助？
