数字构造类题目通用解题思路数字构造题通常为答案不唯一核心是「找规律、用性质、造模式」而非暴力枚举。以下是通用思考路径1. 看数据范围定方向若参数极大如a ≤ 10 9 a\le 10^9a≤109、n ≤ 10 5 n\le 10^5n≤105必然是 (O(1))公式或 (O(n)) 线性构造不可能涉及枚举或高精度运算。若范围较小可以先暴力打表找可行解观察共同特征再提炼通用模式。2. 善用特殊数的性质构造题中最常用的特殊结构全9数9, 99, 999…对应纯循环小数循环节长度等于位数常用于小数位控制数字重复等场景。移位叠加数10 k , 10 k 1 , 10 k − 1 10^k, 10^k1, 10^k-110k,10k1,10k−1乘法具有移位、拼接、叠加的性质适合构造乘积的数位模式。交替序列1212…、abab…天然满足「相邻不同」约束是数位规则题的基础结构。3. 拆分约束逐个满足构造题通常有多个约束条件不要试图一步到位先满足核心约束如「第a位是b」「乘积仅含123」再调整满足次要约束如互质、位数、真分数、数字全出现边界情况单独处理如 (b0)、(n1)一般情况用统一模板。4. 从小样例验证推广手动计算 n2、n3 等小规模情况观察可行解的共同特征提炼出通用构造模式再验证推广到大规模的正确性。5. 优先寻找「平凡解」多数构造题存在非常简洁的构造方式不要过度复杂化。题目保证有解时优先选择最容易实现、最容易验证正确性的构造方案。一、魔法人偶的十进制校准D-魔法人偶的十进制校准_牛客周赛 Round 130题目大意给定正整数a aa可达10 9 10^9109和数字b ( 0 ≤ b ≤ 9 ) b\ (0\le b\le9)b(0≤b≤9)构造最简真分数x y \frac{x}{y}yx满足1 ≤ x y ≤ 1000 1\le x y \le 10001≤xy≤1000gcd ( x , y ) 1 \gcd(x,y)1gcd(x,y)1分数的十进制小数展开中小数点后第a aa位数字恰好为b bb有限小数末尾视为无限个0核心思路由于a aa可以达到10 9 10^9109无法通过逐位计算得到第a aa位数字。本题的核心突破口是利用纯循环小数的周期性选择循环节长度极短的分数如循环节长度为1或2此时第a aa位数字仅由a aa对循环节长度取模决定与a aa的绝对大小无关从而可以轻松控制任意位置的数字。从数学上看分数x y \frac{x}{y}yx小数点后第a aa位数字等价于d a ⌊ x ⋅ 10 a y ⌋ m o d 10 d_a \left\lfloor \frac{x \cdot 10^a}{y} \right\rfloor \bmod 10da⌊yx⋅10a⌋mod10对于纯循环小数该值随a aa呈周期变化。构造方案所有方案均满足y ≤ 1000 y\le 1000y≤1000且gcd ( x , y ) 1 \gcd(x,y)1gcd(x,y)1分情况构造如下1. 数字b ∈ { 1 , 2 , 4 , 5 , 7 , 8 } b \in \{1,2,4,5,7,8\}b∈{1,2,4,5,7,8}直接构造分数b 9 \frac{b}{9}9b分数值为0. b ˙ 0.\dot{b}0.b˙循环节长度为1任意位置的小数位都是b bb天然满足第a aa位为b bb。由于b bb不是3的倍数因此gcd ( b , 9 ) 1 \gcd(b,9)1gcd(b,9)1满足最简分数要求。2. 数字b 3 b3b3或b 6 b6b6b 3 b3b3构造1 3 \frac{1}{3}31值为0. 3 ˙ 0.\dot{3}0.3˙任意位都是3且gcd ( 1 , 3 ) 1 \gcd(1,3)1gcd(1,3)1。b 6 b6b6构造2 3 \frac{2}{3}32值为0. 6 ˙ 0.\dot{6}0.6˙任意位都是6且gcd ( 2 , 3 ) 1 \gcd(2,3)1gcd(2,3)1。注若直接使用3 9 \frac{3}{9}93或6 9 \frac{6}{9}96则不满足互质条件因此输出约分后的形式。3. 数字b 9 b9b9无法使用分母9构造9 9 1 \frac{9}{9}1991不是真分数改用分母99循环节长度为2若a aa为奇数构造91 99 \frac{91}{99}9991值为0. 9 ˙ 1 ˙ 0.\dot{9}\dot{1}0.9˙1˙所有奇数位均为9偶数位均为1。若a aa为偶数构造19 99 \frac{19}{99}9919值为0. 1 ˙ 9 ˙ 0.\dot{1}\dot{9}0.1˙9˙所有偶数位均为9奇数位均为1。互质性验证gcd ( 91 , 99 ) 1 \gcd(91,99)1gcd(91,99)1gcd ( 19 , 99 ) 1 \gcd(19,99)1gcd(19,99)1均满足条件。4. 数字b 0 b0b0利用有限小数或循环小数的0位若a ≥ 2 a\ge2a≥2构造1 2 \frac{1}{2}21值为0.5000 ⋯ 0.5000\cdots0.5000⋯从第2位开始全为0满足要求。若a 1 a1a1构造1 11 \frac{1}{11}111值为0. 0 ˙ 9 ˙ 0.\dot{0}\dot{9}0.0˙9˙第1位为0满足要求。参考代码#includeiostream#defineintlonglongusingnamespacestd;signedmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intt,a,b;cint;while(t--){cinab;if(b0){if(a1)cout1 11\n;elsecout1 2\n;}elseif(b3){cout1 3\n;}elseif(b6){cout2 3\n;}elseif(b9){if(a1)cout91 99\n;elsecout19 99\n;}else{coutb 9\n;}}return0;}二、小彩的好数构造F-小彩的好数构造_牛客周赛 Round 114题目大意给定正整数n nn构造两个n nn位正整数a aa和b bb使得a × b a\times ba×b的结果是「好数」数位仅由1、2、3组成且三个数字都必须出现任意相邻数位的数字互不相同。若不存在解则输出− 1 -1−1。n nn可达2 × 10 5 2\times 10^52×105需线性时间构造。核心思路本题属于大位数构造题核心思想是利用特殊结构数的乘法性质避免高精度运算通过设计乘数的结构直接保证乘积满足好数约束。我们选择形如10 n − 1 1 10^{n-1}110n−11即1后接n − 2 n-2n−2个0再末尾接1的数作为第一个乘数它的乘法性质为一个数X XX乘以10 k 1 10^k 110k1等价于将X XX左移k kk位后与自身相加即乘积 X × 10 k X X \times 10^k XX×10kX。若第二个数本身是仅含两种数字的交替序列那么相加后只会在中间重叠位置产生第三个数字整体仍保持数位只有1、2、3且相邻不同。构造方案边界情况当 (n1) 时两个1位数相乘最大为9 × 9 81 9\times9819×981无法同时包含1、2、3三个数字直接输出− 1 -1−1。一般构造第一个数a aa固定为1( n − 2 ) (n-2)(n−2)个01即a 10 n − 1 1 a 10^{n-1} 1a10n−11。例(n3) 时为101(n4) 时为1001。第二个数b bb构造为交替数字序列若n nn为偶数构造1212…121和2交替共n nn位。若n nn为奇数构造1313…1311和3交替共n nn位。正确性验证偶数示例(n4)(a1001) (b1212)乘积1212 × 1001 1212000 1212 1213212 1212 \times 1001 1212000 1212 12132121212×1001121200012121213212数位序列1 2 1 3 2 1 2仅含1、2、3相邻均不同且三个数字都存在。奇数示例(n3)(a101) (b131)乘积131 × 101 13100 131 13231 131 \times 101 13100 131 13231131×1011310013113231数位序列1 3 2 3 1仅含1、2、3相邻均不同。本质上交替序列本身保证了相邻数字不同中间相加的位置恰好生成第三个数字且与左右两侧数字均不同因此整体满足所有约束。参考代码#includeiostream#includestringusingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;cinn;if(n1){cout-1\n;return0;}// 构造第一个数string a1string(n-2,0)1;// 构造第二个数string b;if(n1){for(inti0;in;i){b(i%20)?1:3;}}else{for(inti0;in;i){b(i%20)?1:2;}}couta b\n;return0;}
