数字构造类题目通用解题思路

数字构造题通常为答案不唯一，核心是「找规律、用性质、造模式」，而非暴力枚举。以下是通用思考路径：

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^k+1, 10^k-110k,10k+1,10k−1）：乘法具有移位、拼接、叠加的性质，适合构造乘积的数位模式。
• 交替序列（1212…、abab…）：天然满足「相邻不同」约束，是数位规则题的基础结构。

3. 拆分约束，逐个满足

构造题通常有多个约束条件，不要试图一步到位：

1. 先满足核心约束（如「第a位是b」「乘积仅含123」）；
2. 再调整满足次要约束（如互质、位数、真分数、数字全出现）；
3. 边界情况单独处理（如 (b=0)、(n=1)），一般情况用统一模板。

4. 从小样例验证推广

手动计算 n=2、n=3 等小规模情况，观察可行解的共同特征，提炼出通用构造模式，再验证推广到大规模的正确性。

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. 1 ≤ x < y ≤ 1000 1\le x < y \le 10001≤x<y≤1000
2. gcd ⁡ ( x , y ) = 1 \gcd(x,y)=1gcd(x,y)=1
3. 分数的十进制小数展开中，小数点后第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 b=3b=3或b = 6 b=6b=6

• b = 3 b=3b=3：构造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 b=6b=6：构造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 b=9b=9

无法使用分母9构造（9 9 = 1 \frac{9}{9}=199​=1不是真分数），改用分母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)=1，gcd ⁡ ( 19 , 99 ) = 1 \gcd(19,99)=1gcd(19,99)=1，均满足条件。

4. 数字b = 0 b=0b=0

利用有限小数或循环小数的0位：

• 若a ≥ 2 a\ge2a≥2：构造1 2 \frac{1}{2}21​，值为0.5000 ⋯ 0.5000\cdots0.5000⋯，从第2位开始全为0，满足要求。
• 若a = 1 a=1a=1：构造1 11 \frac{1}{11}111​，值为0. 0 ˙ 9 ˙ 0.\dot{0}\dot{9}0.0˙9˙，第1位为0，满足要求。

参考代码

#include<iostream>#defineintlonglongusingnamespacestd;signedmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intt,a,b;cin>>t;while(t--){cin>>a>>b;if(b==0){if(a==1)cout<<"1 11\n";elsecout<<"1 2\n";}elseif(b==3){cout<<"1 3\n";}elseif(b==6){cout<<"2 3\n";}elseif(b==9){if(a&1)cout<<"91 99\n";elsecout<<"19 99\n";}else{cout<<b<<" 9\n";}}return0;}

二、小彩的好数构造

F-小彩的好数构造_牛客周赛 Round 114

题目大意

给定正整数n nn，构造两个n nn位正整数a aa和b bb，使得a × b a\times ba×b的结果是「好数」：

1. 数位仅由1、2、3组成，且三个数字都必须出现；
2. 任意相邻数位的数字互不相同。
   若不存在解则输出− 1 -1−1。n nn可达2 × 10 5 2\times 10^52×105，需线性时间构造。

核心思路

本题属于大位数构造题，核心思想是利用特殊结构数的乘法性质，避免高精度运算，通过设计乘数的结构直接保证乘积满足好数约束。

我们选择形如10 n − 1 + 1 10^{n-1}+110n−1+1（即1后接n − 2 n-2n−2个0再末尾接1）的数作为第一个乘数，它的乘法性质为：

一个数X XX乘以10 k + 1 10^k + 110k+1，等价于将X XX左移k kk位后与自身相加，即乘积 =X × 10 k + X X \times 10^k + XX×10k+X。

若第二个数本身是仅含两种数字的交替序列，那么相加后只会在中间重叠位置产生第三个数字，整体仍保持数位只有1、2、3且相邻不同。

构造方案

边界情况

当 (n=1) 时，两个1位数相乘最大为9 × 9 = 81 9\times9=819×9=81，无法同时包含1、2、3三个数字，直接输出− 1 -1−1。

一般构造

1. 第一个数a aa：固定为1+( n − 2 ) (n-2)(n−2)个0+1，即a = 10 n − 1 + 1 a = 10^{n-1} + 1a=10n−1+1。

   • 例：(n=3) 时为101，(n=4) 时为1001。

2. 第二个数b bb：构造为交替数字序列：

   • 若n nn为偶数：构造1212…12（1和2交替），共n nn位。
   • 若n nn为奇数：构造1313…131（1和3交替），共n nn位。

正确性验证

• 偶数示例（(n=4)）：
  (a=1001)， ，，(b=1212)
  乘积：1212 × 1001 = 1212000 + 1212 = 1213212 1212 \times 1001 = 1212000 + 1212 = 12132121212×1001=1212000+1212=1213212
  数位序列：1 2 1 3 2 1 2，仅含1、2、3，相邻均不同，且三个数字都存在。

• 奇数示例（(n=3)）：
  (a=101)， ，，(b=131)
  乘积：131 × 101 = 13100 + 131 = 13231 131 \times 101 = 13100 + 131 = 13231131×101=13100+131=13231
  数位序列：1 3 2 3 1，仅含1、2、3，相邻均不同。

本质上，交替序列本身保证了相邻数字不同，中间相加的位置恰好生成第三个数字，且与左右两侧数字均不同，因此整体满足所有约束。

参考代码

#include<iostream>#include<string>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;cin>>n;if(n==1){cout<<-1<<'\n';return0;}// 构造第一个数string a="1"+string(n-2,'0')+"1";// 构造第二个数string b;if(n&1){for(inti=0;i<n;++i){b+=(i%2==0)?'1':'3';}}else{for(inti=0;i<n;++i){b+=(i%2==0)?'1':'2';}}cout<<a<<' '<<b<<'\n';return0;}