小 Y 非常喜欢自然数，尤其是在学习了两个自然数相除以后。 当然学习了一个新知识，难免会有些得意，他声称他取了两个自然数 a,b （0<a<b<10 6 ），用 a 除以 b 后，得到了一个小数点后有 n 位的非循环小数。可惜的是，他不记得 a 和 b 具体是多少了。 请你验证这种情况是否可能，如果可能，请输出这样的数字 a 和 b 。 第一行包含一个整数 n ，表示商的 n 位小数。 第二行包含 n 个数字，即答案中小数点后的数字，保证不全为 0。 如果不存在这样的解，输出NO； 如果存在解，输出YES，然后换行输出小 Y 使用的两个自然数 a 和 b。必须满足 0<a<b<10 6 。如果有多组解，输出其中任意一个。 用c++实现

<think>题目要求：给定n和n个数字（表示小数部分），问是否存在两个自然数a,b（0<a<b<10^6），使得a/b的小数部分恰好是给定的n位数字（非循环小数）。注意是非循环小数，也就是说这个小数是有限小数。 有限小数：一个分数a/b（最简分数）能表示为有限小数的充要条件是：分母b的质因数只含有2和5。 但是题目中并没有说a/b是最简分数，所以我们需要考虑的是：存在一个分数a/b（不一定最简）使得小数部分恰好是给定的n位数字，并且分母b在约分后其质因数只含2和5（因为非循环小数要求分母只含2和5的因子，且这里分母b可能不是最简形式，但约分后的分母必须满足这个条件）。 然而，题目要求a和b满足0<a<b<10^6，并且b>a，所以a/b是一个真分数。 设给定的n位数字为d1,d2,...,dn，那么小数部分可以表示为0.d1d2...dn = X / (10^n) [其中X是一个整数，即d1d2...dn这个数] 但是注意，a/b不一定等于X/(10^n)，因为a/b可能可以约分。实际上，我们有： a/b = X / (10^n) ? 不一定，因为a/b可能是一个约分后的分数，而X/(10^n)可能还可以约分。 实际上，我们要求：存在整数a,b满足： a / b = k + (X / (10^n)) 其中k是整数部分，但是因为0<a<b，所以a/b<1，因此k=0。 所以：a/b = X/(10^n) 但是，这要求a/b就是X/(10^n)，那么a和b必须满足：a = X * b / (10^n) 是整数，且0<a<b<10^6。 然而，我们也可以这样考虑：设a/b = X/(10^n) 不一定成立，因为a/b可能是一个约分后的分数，而X/(10^n)是约分前的分数？不对，实际上，我们得到的小数点后n位数字就是X，那么a/b应该等于X/(10^n)加上一个误差？不，应该是精确等于。 但是，如果a/b不是最简分数，那么我们可以设a/b = t * (X/(10^n))，这显然不对。实际上，我们只能得到： a/b = X/(10^n) => a * (10^n) = b * X 所以，我们需要找到两个整数a,b满足： a * (10^n) = b * X 且 0<a<b<10^6。 但是，我们还需要注意：题目要求这个小数是非循环小数，即有限小数。而有限小数要求分母b的质因数只含有2和5（在约分后）。因此，我们还需要保证b的质因数只含2和5（注意，这里b可能不是最简形式的分母，但约分后的分母必须只含2和5）。 然而，在等式a*10^n = b*X中，我们可以将b写成b = a * (10^n) / X。由于a和b都是整数，所以X必须整除a*(10^n)。但a和b都是变量，所以我们可以通过调整a和b来满足。 但是，我们也可以这样考虑：设分数X/(10^n)可以约分，约分后得到最简分数为p/q，那么p和q必须满足：q的质因数只含2和5。那么a和b可以取p和q的倍数，即a = k * p, b = k * q，其中k为正整数，且要满足0<a<b<10^6。 因此，步骤： 1. 将输入的小数部分转换成整数X（长度为n，可能很大，注意n最大是多少？题目没有明确，但n个数字，n最大可能是10^6？但是题目要求b<10^6，所以n不会太大，因为分母b的质因数只含2和5，所以b只能是2^a*5^b，那么b最大为10^6以内，所以n最大大概为log2(10^6)≈20（但实际上2^20约100万，所以n最大可以达到20？不对，因为分母可能是2^a*5^b，那么小数位数n=max(a,b)。而10^6以内最大的n是多少？比如分母为2^19*5^0，那么小数位数就是19；分母为5^6，那么小数位数就是6。所以n最大不超过20？不对，比如分母是2^0*5^19，那么小数位数是19？实际上，分母是2^a*5^b，则小数位数是max(a,b)。而2^19=524288，5^19会非常大（超过10^12），所以分母b最大为10^6，所以b=2^a*5^b<=10^6，那么a和b最大是多少？a最大为log2(10^6)≈20，b最大为log5(10^6)≈8.5（取整8），所以max(a,b)最大为20。因此n最大不超过20？不对，比如分母是2^20，那么20位小数，而2^20=1048576>10^6？不对，题目要求b<10^6，所以分母b最大为999999，所以分母中2的指数最多为19（因为2^19=524288，2^20=1048576>10^6），同理5的指数最多为6（5^6=15625，5^7=78125，5^8=390625，5^9=1953125>10^6，所以最大指数为8？不对，5^8=390625<10^6，5^9=1953125>10^6，所以5的指数最大为8？不对，5^8=390625，5^9就超过10^6了，所以5的指数最大为8？不对，5^6=15625，5^7=78125，5^8=390625，5^9=1953125>10^6，所以最大指数为8？不对，5^8=390625，指数是8，但5^8=390625，所以分母可以是390625，那么小数位数就是8（因为分母中2的指数为0，5的指数为8，所以小数位数为8）。因此n最大可能是8？不对，分母可以同时包含2和5，比如分母为2^10 * 5^10，但是2^10=1024, 5^10=9765625，乘积为1024*9765625=10000000000，显然大于10^6，所以分母不能同时有很高的指数。实际上，分母b=2^a * 5^b，且b<10^6，所以a和b不能同时很大。小数位数n=max(a,b)。所以n最大可能是多少？我们取a=0，b最大为8（因为5^8=390625<10^6，5^9=1953125>10^6，所以b最大指数8）；或者b=0，a最大为19（2^19=524288<10^6，2^20=1048576>10^6，所以a最大19）。因此n最大为19。 但是题目输入的第二行是n个数字，n最大可能为19，所以我们可以将n个数字转换成一个整数X（用字符串读入，然后转成整数，19位数字在long long范围内？19位数字最大为10^19-1，而long long最大为2^63-1≈9e18，所以19位数字可能超出long long（因为10^19>1e18），所以我们需要用大数？但是题目要求b<10^6，所以我们可以用另一种方法。 实际上，我们并不需要直接计算X（因为X可能很大），而是利用分数形式。 重新思考：我们要求a/b = X/(10^n) => a * (10^n) = b * X （式1） 并且b的质因数只含2和5（在约分后）。但是注意，等式（式1）中，我们并不要求a和b互质。所以我们可以将等式写成： a = (b * X) / (10^n) 所以，对于给定的X和n，我们需要找到b（0<b<10^6，且b的质因数只含2和5？注意，这里并不要求b的质因数只含2和5，因为等式（式1）成立，那么分数a/b约分后的分母必须只含2和5。所以我们可以先找到所有分母只含2和5的b（在10^6以内），然后检查是否存在b使得： (b * X) % (10^n) == 0 （即b*X能被10^n整除） 并且a = (b * X) / (10^n) 满足0<a<b。 但是，注意：a = (b * X) / (10^n) 必须是一个整数，且0<a<b。 另外，我们也可以反过来：枚举分母b（b是10^6以内只含质因数2和5的数），然后计算a，再检查a是否满足条件。 步骤： 1. 预处理出所有10^6以内的、只含质因数2和5的数（即b=2^a*5^b，且b<10^6）。这样的数不会太多，因为指数a最大19，b最大8，所以总数不超过20*9=180个。 2. 读入n和n个数字（用一个字符串s表示）。 3. 计算X：将字符串s转换成一个整数（如果n很大，比如19，那么X可能很大，我们可以用字符串表示，但这里我们不用直接计算X，而是用另一种方法：利用模运算？但是等式中有10^n，而n最大19，我们可以用long long，但是10^19超出了long long的范围（在C++中，long long最大为64位，大约1e19）。所以我们需要用高精度？或者避免直接计算大整数。 然而，我们注意到：等式（式1）要求b*X能被10^n整除。但是X是一个n位整数，所以X的范围是[0, 10^n-1]（注意，题目保证不全为0，所以X>=1）。而10^n对于n=19来说，是一个20位数（10^19），我们无法直接计算。 因此，我们需要避免直接计算大整数。我们可以这样考虑： 设M = 10^n，但是M太大，我们无法直接存储。但是我们可以利用模运算的性质？不，这里我们需要判断整除性。 另一种思路：将等式（式1）写成： a * M = b * X 其中M=10^n，X是给定的n位数字。 那么，我们要求：b * X 是 M 的倍数。 注意：M=2^n * 5^n （因为10=2*5） 所以，b * X 必须包含至少n个2和n个5的因子。 而b本身是只含2和5的，设b=2^p * 5^q，那么b * X 中包含的2的因子个数为p + (X中2的因子个数)，5的因子个数为q + (X中5的因子个数)。 因此，我们需要满足： p + (X中2的因子个数) >= n q + (X中5的因子个数) >= n 所以，我们可以先计算X中因子2的个数（记为cnt2_x）和因子5的个数（记为cnt5_x）。然后，对于每个候选的b=2^p*5^q，我们需要： p + cnt2_x >= n => p >= n - cnt2_x q + cnt5_x >= n => q >= n - cnt5_x 如果存在这样的p和q（并且b=2^p*5^q<10^6），那么我们就可以取这个b，然后计算： a = (b * X) / M （其中M=10^n） 但是这里X和M都是大数，我们可以用高精度？或者利用分解？但是注意，我们并不需要实际计算整个数，因为我们已经知道b*X一定包含至少n个2和n个5，所以b*X/(2^n*5^n)一定是整数。而且，这个整数a可以这样计算： a = (b * X) / (10^n) = (2^p * 5^q * X) / (2^n * 5^n) = 2^{p-n} * 5^{q-n} * X [如果p>=n且q>=n，那么指数非负] 但是，注意：X可能还包含其他的因子，所以这样计算出来的a不一定是整数？不对，因为我们在前面已经保证了p>=n-cnt2_x，所以p+cnt2_x>=n，同理q+cnt5_x>=n，所以整个数b*X一定被2^n整除，同理被5^n整除，所以被10^n整除。 但是，我们如何计算a？因为X可能很大，而p-n和q-n可能是负数？不对，p>=n-cnt2_x，但n-cnt2_x可能是负数，所以p>=max(0, n-cnt2_x)，同理q>=max(0, n-cnt5_x)。所以p-n>= -cnt2_x，q-n>= -cnt5_x。但是，我们分解X的时候已经知道X=2^{cnt2_x} * 5^{cnt5_x} * X'，其中X'与2和5互质。所以： a = 2^{p-n} * 5^{q-n} * (2^{cnt2_x} * 5^{cnt5_x} * X') = 2^{p-n+cnt2_x} * 5^{q-n+cnt5_x} * X' 因为p>=n-cnt2_x，所以p-n+cnt2_x>=0，同理q-n+cnt5_x>=0，所以a是整数。 但是，我们仍然需要计算a，而X'可能很大（X'=X/(2^{cnt2_x}*5^{cnt5_x})），所以a可能很大？但是注意，我们要求a<b<10^6，所以a必须小于10^6。 因此，我们可以这样计算： 步骤： 1. 计算X中2的因子个数cnt2_x和5的因子个数cnt5_x（注意，X是字符串，我们可以用高精度除法？但是n最大19，X最多19位，我们可以用字符串转成long long？但是19位可能超出long long（在C++中，unsigned long long最大为1.8e19，而10^19=10000000000000000000，刚好在unsigned long long范围内，因为1e19<1.8e19）。所以我们可以将字符串转成unsigned long long（如果n<=19，则可行；如果n>19，则题目中n最大为19？因为分母b最大为10^6，所以小数位数n最大为19，所以n<=19）。 2. 因此，我们可以将输入的字符串s（长度为n）转成一个unsigned long long整数X。 3. 然后，计算cnt2_x和cnt5_x：对X进行除2和除5，直到不能整除。 4. 枚举p和q：p从max(0, n-cnt2_x)到某个上界（比如p_max，使得2^p<=10^6，且p<=19（因为2^20>10^6）），q从max(0, n-cnt5_x)到q_max（5^q<=10^6，q<=8，因为5^8=390625，5^9=1953125>10^6）。注意：p和q的枚举范围要保证b=2^p*5^q<10^6。 5. 对于每一组(p,q)： b = (unsigned long long)pow(2,p) * (unsigned long long)pow(5,q); // 注意这里要保证不溢出，因为p<=19, q<=8，所以2^19*5^8=524288*390625，这个数很大（约2e14），超出了unsigned long long的范围？不对，2^19=524288, 5^8=390625，乘积为524288*390625=204800000000，这个数2e11，而unsigned long long最大约1.8e19，所以可以存下。 但是，我们要求b<10^6，所以如果b>=10^6，我们就跳过。 6. 然后计算a：因为a = (b * X) / (10^n) [这里10^n我们也可以预先计算，n<=19，所以10^n最大为1e19，在unsigned long long范围内] a = b * X / M; // 其中M=pow(10,n) （注意：这里需要整数除法，且要求b*X能被M整除，前面已经保证了整除性） 7. 检查a是否满足：0<a<b 且 a<10^6, b<10^6（因为b我们已经保证小于10^6，但a可能很大？） 注意：a = b * X / M，由于b>=1，X>=1，所以a>=1。我们需要a<b，即 b * X / M < b => X / M < 1 => X < M 而X是n位整数，所以X的范围是[0, M-1]（因为M=10^n），所以X<M，所以a<b成立。 但是，我们还需要a<10^6？题目要求a和b都小于10^6，且a>0，b>a。所以a必须小于10^6。 因此，如果计算出的a>=10^6，那么这个b就不行。 8. 如果找到一组(a,b)满足所有条件，则输出YES，然后输出a和b。 9. 如果枚举所有b（即所有p,q组合）都没有找到，则输出NO。 但是，这里有一个问题：我们枚举的b=2^p*5^q，而p和q的取值我们是从max(0, n-cnt2_x)开始枚举的，但是注意，b必须小于10^6，所以p和q不能太大。而且，我们枚举的p,q可能使得b很大（超过10^6），所以我们在计算b的时候如果发现b>=10^6，就跳过。 另外，计算b的时候，由于p和q是整数，我们可以预先计算出所有10^6以内的形如2^p*5^q的数，并存储在一个数组里（这样的数不会超过200个）。然后，对于每个这样的b，我们检查： p = b中2的指数，q = b中5的指数 if (p + cnt2_x >= n && q + cnt5_x >= n) { // 则这个b满足整除条件 a = (b * X) / M; if (a < 10^6 && a>0 && a < b) { // 注意a<b已经由a<b*X/M和X<M推出，但这里还是检查一下a<b，因为整数除法可能有精度问题？但这里整除，所以不会有问题。另外a必须小于10^6。 // 输出 } } 注意：我们也可以不预先计算b中2和5的指数，而是直接对b分解（因为b很小，且只有2和5两个因子）。 但是，我们如何得到b中2的指数和5的指数？因为我们枚举的b就是2^p*5^q，所以p和q是已知的。 所以，步骤总结： 1. 读入n，然后读入一个字符串s（长度为n）。 2. 将s转换成unsigned long long类型的X（如果n=0，则X=0，但题目保证不全为0，所以n>=1，且X>=1）。 3. 计算M = pow(10, n) （注意：n<=19，所以可以直接计算） 4. 计算X中因子2的个数cnt2_x：循环除2；因子5的个数cnt5_x：循环除5。 5. 预处理所有10^6以内的、形如2^p*5^q的数（b=2^p*5^q），并记录对应的p和q。注意，同一个b可能有不同的(p,q)组合？不会，因为分解唯一。但是同一个b可能由不同的p,q得到？不会，因为2和5互质，所以分解唯一。 实际上，我们可以枚举p（0~19）和q（0~13？因为5^13>10^6，所以q最大到8？因为5^8=390625<10^6，5^9>10^6，所以q从0到8），然后计算b=2^p*5^q，如果b<=1000000，就保存（b, p, q）。 6. 遍历所有这样的b（以及对应的p,q）： if (p + cnt2_x >= n && q + cnt5_x >= n) { a = (b * X) / M; // 检查a是否为整数？因为前面条件保证了整除，所以a一定是整数。 // 检查a是否小于10^6且大于0且小于b（因为X<M，所以a<b一定成立，但a>=1，因为X>=1，b>=1，M>=10，所以a至少为1？） if (a < 1000000 && a>0) { // 同时a<b已经由计算保证（因为a = b * (X/M) 且 X/M<1，所以a<b） // 注意：这里a必须是整数，且我们前面条件保证了整除，所以a是整数。 // 但是，由于整数除法是截断？不，因为b*X能被M整除，所以除法是精确的。 cout << "YES" << endl; cout << a << " " << b << endl; return 0; } } 7. 如果遍历完都没有，输出"NO"。 但是，这里有一个问题：我们枚举的b都是2^p*5^q的形式，但是题目中的b不一定是最简形式？注意，我们这里枚举的b就是分母，而分数a/b不一定是最简的，所以我们的方法正确。 然而，注意：等式a/b = X/(10^n) 成立，所以a/b的分数形式并不一定是最简的，但是我们的方法中，分母b可以是任意2^p*5^q（只要在10^6以内），所以覆盖了所有可能的分母（因为最简分数的分母只能是2和5的幂次，而我们的分母b可以是任意2^p*5^q，所以包含了所有可能的分母，因为如果分母还有其他的因子，那么约分后分母还是2和5的幂次，而我们的b就是约分后的分母的倍数？不对，我们枚举的b就是分母，所以如果原分数不是最简的，那么我们的b就相当于原分母，而a就是原分子。所以我们的方法正确。 但是，注意：有可能存在多个b满足条件，我们只需要输出任意一个。 另外，注意：M=10^n，当n=19时，M=10000000000000000000（20位数），而unsigned long long最大为18446744073709551615（20位数），所以10^19在unsigned long long的范围内吗？10^19=10000000000000000000，而unsigned long long的最大值大于10^19（因为1e19是1后面19个0，而2^64≈1.8e19>1e19），所以可以表示。 但是，计算b*X：b最大为10^6-1，X最大为10^19-1，所以b*X最大约为10^6 * 10^19 = 10^25，超出了unsigned long long的范围（最大1.8e19）。所以我们需要避免直接计算b*X。 因此，我们需要改变计算a的方法：不能直接计算b*X，因为会溢出。 我们如何计算a = (b * X) / M 而不溢出？ 注意：a = (2^p * 5^q * X) / (2^n * 5^n) = 2^{p-n} * 5^{q-n} * X [但是这里p-n和q-n可能是负数？不对，我们要求p>=n-cnt2_x，q>=n-cnt5_x，所以p-n>=-cnt2_x，q-n>=-cnt5_x，所以指数可能为负？不对，因为前面我们要求p>=n-cnt2_x，但n-cnt2_x可能是负数，所以p>=0，所以p-n>= -n（最小为-19），同理q-n>= -n。所以指数可能是负数，但负数指数意味着分母有2或5的因子，而X中已经包含了cnt2_x和cnt5_x，所以整个表达式还是整数？] 实际上，我们前面已经将X分解为：X = 2^{cnt2_x} * 5^{cnt5_x} * X'（其中X'与10互质），那么： a = 2^{p-n} * 5^{q-n} * (2^{cnt2_x} * 5^{cnt5_x} * X') = 2^{p-n+cnt2_x} * 5^{q-n+cnt5_x} * X' 因为p>=n-cnt2_x -> p+cnt2_x>=n -> 指数p-n+cnt2_x>=0 q>=n-cnt5_x -> q+cnt5_x>=n -> 指数q-n+cnt5_x>=0 所以a= (2^{p-n+cnt2_x} * 5^{q-n+cnt5_x}) * X' 因此，我们可以这样计算a： step1: 计算X' = X / (2^{cnt2_x} * 5^{cnt5_x}) （这里X'是整数，而且与10互质） step2: 计算a = X' * (2^{p-n+cnt2_x}) * (5^{q-n+cnt5_x}) 但是，这里指数可能很大吗？指数p-n+cnt2_x最大是多少？p最大19，n最小1，cnt2_x最大为cnt2_x（不超过n，因为X<10^n，所以因子2的个数最多不超过n? 不对，比如X=2^(n-1)*奇数，那么cnt2_x<=n-1？因为2^n>10^{n}? 不对，2^n和10^n没有直接关系。实际上，X<10^n，所以X中2的因子个数最多为log2(10^n)≈n*log2(10)≈3.32n，所以最大可能为3.32n，而n最大19，所以cnt2_x最大约63，而p最大19，所以p-n+cnt2_x最大为19-1+63=81，那么2^81是一个很大的数（约2.4e24），而a=X' * ...，X'最大为X/(2^{cnt2_x}*5^{cnt5_x})，即X去掉2和5的因子，所以X'最大可能接近10^n（比如X=10^n-1，且不含2和5的因子，那么X'=10^n-1，约为1e19），再乘以2^81，会非常大，所以a可能远远超过10^6。 因此，我们需要避免这种大指数的计算，而是采用另一种方法：在计算过程中判断是否超过10^6。 实际上，我们可以这样计算： a = X' * pow2[p-n+cnt2_x] * pow5[q-n+cnt5_x] 但是，如果p-n+cnt2_x很大，那么pow2[p-n+cnt2_x]可能非常大，而X'也可能很大，导致a很大。所以我们在计算过程中，如果中间结果超过10^6，就可以提前放弃这个b。 但是，我们也可以先计算指数较小的部分，然后乘以X'，并检查是否超过10^6。 由于p-n+cnt2_x>=0，q-n+cnt5_x>=0，所以我们可以分别计算2的幂和5的幂，然后乘上X'。但是指数最大可能80多，而且2的80次方已经很大，所以我们不能直接计算。 因此，我们换一种思路：因为a必须小于10^6，所以如果指数p-n+cnt2_x和q-n+cnt5_x很大，那么显然a会很大，所以我们可以设置指数上限：比如，如果p-n+cnt2_x>40（因为2^40约1e12，再乘以X'（最大1e19）就会非常大），那么我们可以直接跳过。但实际上，我们要求a<10^6，所以如果2^{p-n+cnt2_x} * 5^{q-n+cnt5_x} * X' >= 10^6，那么我们就可以跳过这个b。 但是，我们可以在计算之前先估算：取对数，如果 log10(X') + (p-n+cnt2_x)*log10(2) + (q-n+cnt5_x)*log10(5) > 6，那么a>10^6，跳过。 但是，X'我们还没有计算，而且X'最大为10^n-1（n<=19），所以log10(X')<=19。而指数部分：p-n+cnt2_x<=19+63（但63是理论值，实际上X<10^n，所以cnt2_x<=n*log10(2)? 不对，应该是cnt2_x<=log2(X)<=log2(10^n)=n*log2(10)≈3.32n≈63.08，所以最大63。而p<=19，所以p-n+cnt2_x<=19-1+63=81，所以指数部分的最大值：81*log10(2)≈24.36，加上log10(X')<=19，所以总和最大约43.36，远远大于6（10^6的对数是6），所以大部分情况a都会大于10^6？不对，我们要求a<10^6，所以如果估算值大于6，那么a>10^6，就不行。 因此，我们可以用对数来快速判断：如果 log10(X') + (p-n+cnt2_x)*log10(2) + (q-n+cnt5_x)*log10(5) > 6 + epsilon（比如1e-9），那么跳过。 但是，对数计算可能有精度问题，而且我们需要精确计算？或者，我们可以用整数计算来避免对数？我们可以用乘法来比较，但可能也很麻烦。 另一种思路：因为a<10^6，所以X' * 2^{p-n+cnt2_x} * 5^{q-n+cnt5_x} < 10^6，所以如果2^{p-n+cnt2_x} * 5^{q-n+cnt5_x} >= 10^6，那么a必然大于等于10^6（因为X'>=1），所以我们可以先计算2^{p-n+cnt2_x} * 5^{q-n+cnt5_x}，如果这个值大于等于10^6，则跳过。否则，再乘以X'（此时X'>=1，但乘积可能还是小于10^6？），然后检查。 但是，注意：2^{p-n+cnt2_x} * 5^{q-n+cnt5_x} 可能是一个很大的数（比如指数很大），所以我们需要避免直接计算（可能溢出）。我们可以用循环乘2和乘5，并在过程中判断是否超过10^6，如果超过就跳出。 步骤： temp = 1; exp2 = p - n + cnt2_x; // 需要乘的2的指数 exp5 = q - n + cnt5_x; // 需要乘的5的指数 for(int i=0; i<exp2; i++) { temp *= 2; if (temp > 1000000) break; } if (temp <= 1000000) { for(int i=0; i<exp5; i++) { temp *= 5; if (temp > 1000000) break; } } if (temp > 1000000) { // 那么a=temp * X' >= temp > 10^6，所以跳过 continue; } // 否则，temp<=10^6，那么a = temp * X'，而X'=X/(2^{cnt2_x}*5^{cnt5_x}) （这个X'我们之前已经计算过，是一个整数） a = temp * X_prime; // 然后检查a是否小于10^6 if (a > 1000000) { continue; } 但是，这里有一个问题：X_prime可能很大，导致a=temp * X_prime > 10^6，即使temp很小。所以我们需要在计算a之前，先判断：如果X_prime > 1000000 / temp （整除），那么a>10^6，跳过。否则，a=temp*X_prime。 注意：temp>=1，X_prime>=1。 所以，我们需要计算X_prime：X_prime = X / (2^{cnt2_x} * 5^{cnt5_x}) 而X我们是用unsigned long long存储的，所以可以计算。 因此，步骤： 1. 读入n，字符串s。 2. 将s转成unsigned long long X（如果n>19，则无法用unsigned long long表示，但题目中n最大19，所以可以）。 3. 计算M = pow(10, n) （用unsigned long long，注意n=0时M=1，但n>=1） 4. 计算cnt2_x: 对X（用unsigned long long）不断除2，直到不能整除，记录次数；同理cnt5_x。 5. 计算X_prime = X / (power2[cnt2_x] * power5[cnt5_x]) // 这里power2和power5可以预先计算，但cnt2_x和cnt5_x不大（最大60多），所以我们可以用循环计算，或者用pow函数？但注意，pow(2, cnt2_x)可能很大，但cnt2_x最大为60多，2^60大约1e18，在unsigned long long范围内。但是，如果cnt2_x很大（比如60），那么power2[cnt2_x]可能接近2^60，而X最大为10^19-1，所以X_prime = X/(2^60) 可能大约10^19/(2^60)≈10^19/(1e18)=10，所以不会溢出。所以我们可以直接计算。 unsigned long long base = 1; for(int i=0; i<cnt2_x; i++) base *= 2; for(int i=0; i<cnt5_x; i++) base *= 5; X_prime = X / base; // 注意，这里X必须能被base整除，因为cnt2_x和cnt5_x就是X中2和5的因子个数。 6. 枚举所有b=2^p*5^q（p:0~19, q:0~8，且b<10^6）： if (p>=n-cnt2_x && q>=n-cnt5_x) { // 计算指数 int exp2 = p - n + cnt2_x; // 需要乘的2的指数（非负） int exp5 = q - n + cnt5_x; // 需要乘的5的指数（非负） unsigned long long temp = 1; // 计算2^exp2 * 5^exp5，如果中间结果超过10^6，则跳过 bool flag = true; for(int i=0; i<exp2; i++) { temp *= 2; if (temp > 1000000) { flag = false; break; } } if (!flag) continue; for(int i=0; i<exp5; i++) { temp *= 5; if (temp > 1000000) { flag = false; break; } } if (!flag) continue; // 现在temp<=10^6，那么a = temp * X_prime if (X_prime > 1000000 / temp) { // 即 temp * X_prime > 1000000 continue; } a = temp * X_prime; // 注意：a必须大于0（因为X_prime>=1，temp>=1，所以a>=1）且小于10^6（由上面条件保证），并且b=2^p*5^q（我们枚举的b<10^6） // 且a<b? 由a = (b * X) / M，而X<M，所以a<b，所以满足。 // 所以输出 cout << "YES" << endl; cout << a << " " << b << endl; return 0; } 7. 如果枚举完都不行，输出"NO" 但是，这里有一个细节：b=2^p*5^q，而p和q是整数，我们需要计算b，但我们在枚举p,q时已经可以计算b，并且要求b<10^6。所以我们在枚举p,q时，先计算b=2^p*5^q，如果b>=10^6，则跳过。 所以，完整代码步骤： 1. 读入n，字符串s。 2. 将s转成unsigned long long X（如果n为0，则X=0，但题目保证不全为0，所以n>=1，所以不用考虑n=0）。 3. 计算M = 1; for(int i=0; i<n; i++) M *= 10; （注意：n<=19，所以M可以这样计算） 4. 计算cnt2_x和cnt5_x（对X）。 5. 计算X_prime = X / (2^cnt2_x * 5^cnt5_x) [注意：这里用循环计算2^cnt2_x和5^cnt5_x，然后除，注意整除] 6. 枚举p从0到19，q从0到8： b = (unsigned long long)pow(2,p) * (unsigned long long)pow(5,q); if (b > 1000000) continue; // b<10^6 // 然后检查p>=n-cnt2_x 且 q>=n-cnt5_x if (p>=n-cnt2_x && q>=n-cnt5_x) { // 计算指数 int exp2 = p - n + cnt2_x; int exp5 = q - n + cnt5_x; // 计算temp = 2^exp2 * 5^exp5，并确保不超过10^6 unsigned long long temp = 1; bool flag = true; for(int i=0; i<exp2; i++) { temp *= 2; if (temp > 1000000) { flag = false; break; } } if (!flag) continue; for(int i=0; i<exp5; i++) { temp *= 5; if (temp > 1000000) { flag = false; break; } } if (!flag) continue; // 检查 temp * X_prime <= 1000000 if (temp == 0) continue; // 避免除0，但temp>=1 if (X_prime > 1000000 / temp) continue; a = temp * X_prime; // 此时a<=1000000，且a>0，且b>0，且b<10^6，且a<b（因为X<M，所以a = (b * X) / M < b * (M-1)/M < b） // 所以满足条件 cout << "YES\n" << a << " " << b << endl; return 0; } 7. 输出"NO" 但是，注意：我们枚举的b=2^p*5^q，而p和q的枚举范围是p:0~19，q:0~8，所以b=2^p*5^q可能重复吗？不会，因为2和5互质，所以不同的(p,q)得到不同的b。 但是，注意：当p=0且q=0时，b=1，那么a = (1 * X) / M，而X<M，所以a<1，但a必须是整数，所以a=0，但题目要求a>0，所以b=1时，a=0不满足。所以p和q不会同时为0？因为b=1时，a=0，所以会被跳过（因为a>0不满足）。所以我们需要在枚举时注意，但我们的循环p和q从0开始，所以b=1会被枚举到，但是a=0，所以会被跳过（因为a>0不满足，我们检查a>0）。 另外，注意：当n-cnt2_x为负数时，我们取p>=0，所以p>=0总是成立（因为p>=0）。同理q>=0。 但是，有一个边界：如果n-cnt2_x为负数，那么条件p>=n-cnt2_x自然成立（因为p>=0>n-cnt2_x），同理q>=n-cnt5_x也可能自然成立（如果n-cnt5_x<0）。所以这种情况下，我们只需要p>=0且q>=0（并且b<10^6）就可以考虑。 因此，代码实现： 注意：计算2^cnt2_x和5^cnt5_x时，cnt2_x和cnt5_x可能比较大（最大60多），所以我们需要用循环计算，但注意unsigned long long的范围（最大1.8e19），而2^60大约1e18，5^60非常大，所以不能直接计算5^cnt5_x？不对，cnt5_x是X中5的因子个数，而X<10^n（n<=19），所以cnt5_x最大为log5(X)<=log5(10^19)=19*log5(10)≈19/0.69897≈27.18，所以cnt5_x最大27。那么5^27=7.45e18，在unsigned long long范围内（1.8e19>7.45e18）。所以可以计算。 但是，2^cnt2_x：cnt2_x最大为log2(10^19)≈63.1，所以2^63≈9e18，也在unsigned long long范围内。 所以，计算base = (2^cnt2_x * 5^cnt5_x) 是可行的。 但是，注意：base可能很大，而X最大为10^19-1，所以X/base可能很小（比如cnt2_x=0，cnt5_x=0，则base=1，X_prime=X；如果cnt2_x=60，那么base=2^60，X_prime=X/(2^60)，而X最大10^19，所以X_prime最大10^19/2^60≈10，所以很小）。 因此，代码： 注意：如果X不能被2^cnt2_x*5^cnt5_x整除？不会，因为cnt2_x和cnt5_x就是X中2和5的因子个数，所以一定能整除。 但是，在计算base时，如果cnt2_x和cnt5_x很大，base可能为0（溢出）？但cnt2_x最大63，2^63在unsigned long long范围内（2^64-1是最大值），所以不会溢出。同样，5^cnt5_x最大5^27，也在范围内。 但是，base = power2[cnt2_x] * power5[cnt5_x] 可能溢出吗？最大是2^63 * 5^27，这个数有多大？2^63≈9.2e18，5^27≈7.45e18，乘积约为6.8e37，远远超过unsigned long long的范围（1.8e19），所以会溢出。 因此，我们不能直接计算base = (2^cnt2_x) * (5^cnt5_x)，而是应该先计算2^cnt2_x，然后乘以5^cnt5_x，但这样也会溢出。 所以，我们需要避免同时计算两个大数的乘积。我们可以这样计算X_prime： while (cnt2_x) { if (X % 2 == 0) { X /= 2; cnt2_x--; } else { break; } } while (cnt5_x) { if (X % 5 == 0) { X /= 5; cnt5_x--; } else { break; } } X_prime = X; 这样，我们通过不断除2和除5，得到X_prime。这样避免了计算大数base。 但是，注意：cnt2_x和cnt5_x是我们在除的过程中计数的，所以这样除完后，X_prime就是X去除所有2和5因子后的结果。 所以，步骤5可以改为： unsigned long long X_prime = X; // 先复制X cnt2_x = 0; while (X_prime % 2 == 0) { X_prime /= 2; cnt2_x++; } cnt5_x = 0; while (X_prime % 5 == 0) { X_prime /= 5; cnt5_x++; } // 注意：这里我们重新计算了cnt2_x和cnt5_x，但之前我们已经有了一次计数？不对，我们之前没有计算cnt2_x和cnt5_x，所以这里就是计算的过程。 所以，我们不需要在之前计算cnt2_x和cnt5_x？因为这里我们重新计算了。但是，在条件判断中（p>=n-cnt2_x）我们需要cnt2_x，所以这里我们计算cnt2_x和cnt5_x，并同时得到X_prime。 因此，修改：去掉之前的cnt2_x和cnt5_x的计算，只在这里计算。 步骤5改为： unsigned long long X_prime = X; int cnt2_x = 0, cnt5_x = 0; while (X_prime % 2 == 0) { X_prime /= 2; cnt2_x++; } while (X_prime % 5 == 0) { X_prime /= 5; cnt5_x++; } // 现在X_prime就是去除2和5因子后的部分 注意：这样计算后，X_prime就是X去除2和5因子后的值，并且cnt2_x和cnt5_x分别记录X中2和5的因子个数。 然后，我们继续。 但是，注意：X_prime可能等于0？不会，因为X>=1，而且我们除的都是因子，所以X_prime>=1。 所以，完整代码： 注意：n=0的情况？题目保证不全为0，所以n>=1。 另外，注意：M=10^n，n<=19，所以可以用unsigned long long。 最后，注意：如果输入的小数部分有前导0？比如n=3，输入"001"，那么X=1。所以字符串转整数时，前导0会自动去掉？不对，我们直接转换： string s = "001"; unsigned long long X = stoull(s); // 这样会得到1 但是，题目要求是小数点后的n位数字，所以输入可能是"0...01"（前面有0），所以用stoull会去掉前导0，所以不行。 所以，我们需要保留所有的n位数字，包括前导0。但是，stoull会忽略前导0，所以我们需要用字符串的长度为n，如果转换后数字的位数少于n，说明有前导0，那么X就是字符串表示的数字（包括前导0，但stoull会去掉）。所以不能直接用stoull。 因此，我们可以这样：如果字符串s有前导0，那么X就是s表示的数（比如"001"表示1），但是我们在计算时，X=1，而n=3，所以M=1000，那么a/b=1/1000=0.001，符合题意。所以用stoull(s)得到1，是正确的。 但是，如果s全0？题目保证不全为0，所以至少有一个非0。 所以，我们可以用：X = stoull(s); // 这样会忽略前导0，得到后面的数字，这符合数值表示。 但是，如果n很大，比如19，而s前面有18个0，最后一个是1，那么X=1，这样我们计算时，a/b=1/10^19，那么分母b=10^19，但是b必须小于10^6，所以不可能。所以这种情况应该输出NO。 因此，我们的算法中，如果s有前导0，那么X很小，而n很大，那么条件p>=n-cnt2_x和q>=n-cnt5_x就很难满足（因为n很大，而cnt2_x和cnt5_x很小，所以需要p和q很大，但b=2^p*5^q<10^6，所以p和q不能太大），所以可能输出NO。 所以，用stoull(s)得到X，然后计算cnt2_x和cnt5_x，以及X_prime，然后枚举p,q。 但是，注意：如果s是"000...01"，那么X=1，cnt2_x=0，cnt5_x=0，X_prime=1，那么条件：p>=n, q>=n。而b=2^p*5^q<10^6，且n可能很大（比如19），那么p>=19，q>=19，那么b>=2^19*5^19，这个数非常大，远大于10^6，所以没有满足条件的b。所以输出NO，正确。 因此，代码： 1. 读入n。 2. 读入字符串s（长度为n）。 3. 将s转成unsigned long long X：如果s长度大于0，则X = stoull(s); 但注意，如果s很长（比如19位）且全是0，那么X=0，但题目保证不全0，所以不会出现0。如果s有前导0，stoull会忽略，所以X就是去掉前导0后的整数。 4. 计算M = 1; for (int i = 0; i < n; i++) { M *= 10; } 5. 计算cnt2_x, cnt5_x, X_prime: unsigned long long X_prime = X; int cnt2_x = 0, cnt5_x = 0; while (X_prime % 2 == 0) { X_prime /= 2; cnt2_x++; } while (X_prime % 5 == 0) { X_prime /= 5; cnt5_x++; } 6. 枚举p:0~19, q:0~8: b = 1; // 计算2^p for(int i=0; i<p; i++) { b *= 2; if (b > 1000000) break; } if (b > 1000000) continue; // 计算b*5^q unsigned long long b_temp = b; for(int i=0; i<q; i++) { b_temp *= 5; if (b_temp > 1000000) break; } if (b_temp > 1000000) continue; b = b_temp; // 现在b=2^p*5^q，且b<10^6 if (p>=n-cnt2_x && q>=n-cnt5_x) { // 计算指数 int exp2 = p - n + cnt2_x; int exp5 = q - n + cnt5_x; // 计算temp = 2^exp2 * 5^exp5 unsigned long long temp = 1; bool flag = true; for(int i=0; i<exp2; i++) { temp *= 2; if (temp > 1000000) { flag = false; break; } } if (!flag) continue; for(int i=0; i<exp5; i++) { temp *= 5; if (temp > 1000000) { flag = false; break; } } if (!flag) continue; // 检查 temp * X_prime <= 1000000 if (temp == 0) continue; // 实际上temp>=1 if (X_prime > 1000000 / temp) continue; a = temp * X_prime; // 满足条件，输出 cout << "YES" << endl; cout << a << " " << b << endl; return 0; } 7. 输出"NO" 但是，这里有一个问题：exp2和exp5可能是负数？不会，因为p>=n-cnt2_x，所以exp2>=0，同理exp5>=0。 所以，我们不需要处理负数指数。 但是，注意：当n-cnt2_x为负数时，p>=0，所以exp2 = p - n + cnt2_x >=0 成立（因为p>=0，且cnt2_x>=n? 不，n-cnt2_x为负数，所以cnt2_x>n，所以exp2 = p - n + cnt2_x >=0 + (cnt2_x - n) >0）。所以exp2>=0，同理exp5>=0。 因此，我们只需要计算非负指数的幂。 但是，还有一种情况：如果n=0？题目中n>=1，所以不考虑。 最后，注意：有可能X=0？但题目保证不全为0，所以X>=1。 所以，我们按照上述步骤编写代码。 但是，注意：在计算b=2^p*5^q时，我们用了两个循环，先乘2再乘5，这样计算b。 另外，在枚举p和q时，我们也可以预先计算好所有不超过10^6的2^p*5^q，然后存储在一个vector中，并记录p和q。这样避免重复计算。但是因为p和q的枚举范围很小（20*9=180），所以直接枚举即可。 但是，在循环中，我们可能会多次计算2^p，所以可以预先计算2的幂和5的幂的数组。 优化：预先计算power2[0..19]和power5[0..8]（用unsigned long long），然后枚举p,q时，b = power2[p] * power5[q]，然后判断b<10^6。 所以，可以预先计算： unsigned long long power2[20], power5[10]; power2[0]=1; for(int i=1;i<=19;i++) power2[i]=power2[i-1]*2; power5[0]=1; for(int i=1;i<=8;i++) power5[i]=power5[i-1]*5; 然后，枚举p:0..19, q:0..8: b = power2[p] * power5[q]; if (b>1000000) continue; 这样更高效。 因此，最终代码： 1. 预处理power2和power5数组。 2. 读入n，字符串s，将s转成X（unsigned long long）。 3. 计算M（10^n）。 4. 计算X_prime, cnt2_x, cnt5_x（通过不断除2和5）。 5. 枚举p=0..19, q=0..8: b = power2[p] * power5[q]; if (b>1000000) continue; if (p>=n-cnt2_x && q>=n-cnt5_x) { exp2 = p - n + cnt2_x; exp5 = q - n + cnt5_x; // 计算temp = power2[exp2] * power5[exp5] 但是注意，exp2可能大于19（但p<=19, n>=1, cnt2_x>=0，所以exp2<=19+n? 不对，exp2=p-n+cnt2_x，而p<=19，所以exp2<=19-1+cnt2_x，而cnt2_x最大为多少？之前我们计算了cnt2_x，它不会超过log2(X)，而X<10^n，所以cnt2_x<=n*log2(10)≈3.32n，n<=19，所以cnt2_x<=63，所以exp2最大为19-1+63=81，所以可能大于19，所以不能直接用power2[exp2]（因为数组只到19）） } // 所以，我们还是要用循环计算temp，或者用另一个方法：因为exp2和exp5可能很大，所以用循环计算并判断是否超过10^6。 所以，还是用循环计算temp。 因此，代码： 注意：exp2和exp5是非负整数，且exp2最大81，exp5最大81？不对，exp5 = q - n + cnt5_x，q<=8，n>=1，cnt5_x<=log5(X)<=log5(10^n)=n*log5(10)≈27.18，所以exp5<=8-1+27=34。所以最大34，所以循环次数最多34次，可以接受。 所以，最终代码： 注意：为了避免重复计算，我们预先计算power2和power5数组只用于计算b，而temp的计算用循环。 代码结构： #include <iostream> #include <string> #include <cmath> #include <vector> #include <cctype> #include <algorithm> using namespace std; int main() { // 预处理2的幂（0~19）和5的幂（0~8） unsigned long long power2[20], power5[10]; power2[0] = 1; for (int i = 1; i <= 19; i++) { power2[i] = power2[i-1] * 2; } power5[0] = 1; for (int i = 1; i <= 8; i++) { power5[i] = power5[i-1] * 5; } int n; cin >> n; string s; cin >> s; // 长度为n // 将s转换成unsigned long long // 注意：s可能包含前导0，但stoull会忽略 unsigned long long X = 0; if (s.length() > 0) { X = stoull(s); // 如果s为空，则X=0，但n>=1，所以s非空 } // 但是，如果s的长度小于n，说明输入有问题？题目保证第二行有n个数字，所以s.length()==n // 计算 M = 10^n unsigned long long M = 1; for (int i = 0; i < n; i++) { M *= 10; } // 计算X_prime, cnt2_x, cnt5_x unsigned long long X_prime = X; int cnt2_x = 0, cnt5_x = 0; // 注意：如果X=0，则循环会卡住？但题目保证不全0，所以X>=1 while (X_prime % 2 == 0) { X_prime /= 2; cnt2_x++; } while (X_prime % 5 == 0) { X_prime /= 5; cnt5_x++; } // 现在X_prime就是去除2和5因子后的数 // 枚举p和q for (int p = 0; p <= 19; p++) { for (int q = 0; q <= 8; q++) { unsigned long long b = power2[p] * power5[q]; if (b > 1000000) continue; // b超过10^6，跳过 // 检查p和q是否满足条件 if (p >= n - cnt2_x && q >= n - cnt5_x) { int exp2 = p - n + cnt2_x; int exp5 = q - n + cnt5_x; // exp2和exp5非负 unsigned long long temp = 1; bool flag = true; // 计算2^exp2 for (int i = 0; i < exp2; i++) { temp *= 2; if (temp > 1000000) { flag = false; break; } } if (!flag) continue; // 计算5^exp5 for (int i = 0; i < exp5; i++) { temp *= 5; if (temp > 1000000) { flag = false; break; } } if (!flag) continue; // 检查temp * X_prime <= 1000000 if (temp == 0) { // 实际上temp>=1，所以可以不要 continue; } // 注意：X_prime>=1，temp>=1 if (X_prime > 1000000 / temp) { continue; } unsigned long long a = temp * X_prime; // 满足条件：a>0, a<10^6, a<b（由a = (b*X)/M，且X<M，所以a<b，这里不检查a<b，因为题目只要求0<a<b<10^6，我们确保a<b<10^6，但a<b由a<b*X/M< b*1 =b 保证） // 输出 cout << "YES" << endl; cout << a << " " << b << endl; return 0; } } } cout << "NO" << endl; return 0; } 但是，有一个边界：当n-cnt2_x为负数时，条件p>=n-cnt2_x自动满足（因为p>=0），所以条件简化为q>=n-cnt5_x。同理。 所以，代码正确。 测试：n=1, s="5" -> X=5, M=10 cnt2_x: 5%2!=0 ->0; cnt5_x: 5%5=0 -> 5/5=1 -> cnt5_x=1; 然后X_prime=1. 条件：p>=1-0=1, q>=1-1=0. 枚举p>=1, q>=0: b = 2^p * 5^q, 且b<10^6. 取p=1,q=0: b=2 -> 满足条件。 exp2 = 1-1+0=0, exp5=0-1+1=0 -> temp=1. a = 1 * 1 = 1. 输出：YES, 1 2 -> 1/2=0.5，但题目要求小数部分为5（只有1位），而1/2=0.5，所以小数部分为"5"，符合。 但是，1/2=0.5，而题目要求小数部分为5（n=1），所以正确。 再测试：n=2, s="10" -> X=10, M=100. cnt2_x: 10/2=5 -> 5不是偶数，所以cnt2_x=1? 不对，10%2=0 -> 10/2=5 -> 5%2!=0 -> cnt2_x=1. cnt5_x: 5%5=0 -> 5/5=1 -> cnt5_x=1. X_prime=1. 条件：p>=2-1=1, q>=2-1=1. 枚举：p>=1, q>=1 -> 取p=1,q=1: b=2*5=10. exp2=1-2+1=0, exp5=1-2+1=0 -> temp=1. a=1. 输出：YES, 1 10 -> 1/10=0.1，小数部分为"1"（只有1位），但题目要求2位，所以应该是0.10，但题目要求小数点后n位，所以应该是"10"？不对，1/10=0.10，但是小数部分最后一位0可能被省略？题目要求是n位小数，所以1/10写成0.10（保留两位）就是0.10，所以小数部分为"10"。 所以正确。 但是，注意：1/10=0.1，在计算机中可能表示为0.100000...，所以小数部分就是1后面跟着0。题目要求小数点后n位，所以就是"10"（n=2）。 所以，输出正确。 再测试：n=3, s="000" -> 题目保证不全0，所以不会出现。 测试：n=3, s="001" -> X=1, M=1000. cnt2_x=0, cnt5_x=0, X_prime=1. 条件：p>=3, q>=3. 枚举：p>=3, q>=3：最小的b=2^3*5^3=8*125=1000. 然后exp2=3-3+0=0, exp5=3-3+0=0, temp=1, a=1. 输出：1 1000 -> 1/1000=0.001，小数部分为"001"，符合。 测试：n=3, s="002" -> X=2, cnt2_x=1 (因为2%2=0, 2/2=1 -> 1不是2的倍数，所以cnt2_x=1), cnt5_x=0, X_prime=1. 条件：p>=3-1=2, q>=3-0=3. 取p=2,q=3: b=4*125=500. exp2=2-3+1=0, exp5=3-3+0=0, temp=1, a=1. 输出：1 500 -> 1/500=0.002，小数部分为"002"，符合。 所以，代码正确。 但是，注意：n=3, s="123" -> X=123, cnt2_x: 123是奇数，所以0； cnt5_x: 123%5!=0，所以0； X_prime=123. 条件：p>=3, q>=3. 取p=3,q=3: b=8*125=1000. exp2=3-3+0=0, exp5=3-3+0=0, temp=1, a=123. 检查：a=123<1000，且a<10^6，所以输出：123 1000 -> 123/1000=0.123，小数部分为"123"，符合。 因此，我们编写代码。 注意：当n=0时，题目不会出现，所以不考虑。 但是，题目要求0<a<b<10^6，所以a和b都要小于10^6，且a>0，b>a。 最后，注意：如果字符串s对应的X等于0？但题目保证不全0，所以X>=1。 所以，代码实现如下： 注意：在计算temp时，如果exp2=0或exp5=0，循环不会执行，所以temp=1。 另外，注意：如果exp2=0且exp5=0，那么temp=1。 我们提交时，注意使用C++11或更高版本（因为使用了stoull）。 但是，如果n>19，那么M=10^n会溢出（因为n>19时，10^n>10^19，而unsigned long long最大约1.8e19，所以n=20时，M就溢出了）。但题目中n最大为19（因为分母b<10^6，所以小数位数n最大为19），所以n<=19，安全。 所以，最终代码：</think>以下是使用C++实现的解决方案。该程序验证是否存在两个自然数a和b（0 < a < b < 10^6），使得a/b的小数部分恰好是给定的n位非循环小数。如果存在，输出YES和任意一组a、b；否则输出NO。 ```cpp #include <iostream> #include <string> #include <cctype> #include <vector> #include <cmath> #include <algorithm> #include <cstdlib> using namespace std; int main() { // Precompute powers of 2 and 5 unsigned long long power2[20]; power2[0] = 1; for (int i = 1; i <= 19; i++) { power2[i] = power2[i-1] * 2; } unsigned long long power5[10]; power5[0] = 1; for (int i = 1; i <= 8; i++) { power5[i] = power5[i-1] * 5; } int n; cin >> n; string s; cin >> s; // Convert string to unsigned long long unsigned long long X = 0; if (s.length() > 0) { X = stoull(s); // Converts string to unsigned long long, ignoring leading zeros } // Calculate M = 10^n unsigned long long M = 1; for (int i = 0; i < n; i++) { M *= 10; } // Compute X_prime, cnt2_x, cnt5_x unsigned long long X_prime = X; int cnt2_x = 0, cnt5_x = 0; while (X_prime % 2 == 0) { X_prime /= 2; cnt2_x++; } while (X_prime % 5 == 0) { X_prime /= 5; cnt5_x++; } // Iterate over possible p and q for (int p = 0; p <= 19; p++) { for (int q = 0; q <= 8; q++) { unsigned long long b = power2[p] * power5[q]; if (b > 1000000 || b == 0) continue; if (p >= n - cnt2_x && q >= n - cnt5_x) { int exp2 = p - n + cnt2_x; int exp5 = q - n + cnt5_x; unsigned long long temp = 1; bool flag = true; for (int i = 0; i < exp2; i++) { temp *= 2; if (temp > 1000000) { flag = false; break; } } if (!flag) continue; for (int i = 0; i < exp5; i++) { temp *= 5; if (temp > 1000000) { flag = false; break; } } if (!flag) continue; if (temp == 0) continue; if (X_prime > 1000000 / temp) { continue; } unsigned long long a = temp * X_prime; if (a > 0 && a < 1000000 && a < b) { cout << "YES" << endl; cout << a << " " << b << endl; return 0; } } } } cout << "NO" << endl; return 0; } ``` ### 算法说明 1. **预处理**：预先计算2的幂（0到19次方）和5的幂（0到8次方），这些值用于生成分母b的候选值。 2. **输入处理**：读取小数位数n和表示小数部分的字符串s，将其转换为整数X（忽略前导零）。 3. **计算M**：计算10^n，用于后续的分数转换。 4. **分解因子**：计算X中因子2和5的个数（cnt2_x, cnt5_x），并得到去除这些因子后的值X_prime。 5. **枚举分母b**：遍历所有可能的b（形式为2^p * 5^q且小于10^6），检查是否满足条件： - 条件：p ≥ n - cnt2_x 且 q ≥ n - cnt5_x（确保分母b能整除10^n）。 6. **计算分子a**：对于每个候选b，计算分子a = (b * X) / (10^n)，并验证a是否满足0 < a < b < 10^6。 7. **输出结果**：如果找到符合条件的a和b，输出"YES"和它们的值；否则输出"NO"。 ### 注意事项 - 程序使用`stoull`处理字符串转换，自动忽略前导零。 - 由于n最大为19，10^n在`unsigned long long`范围内（最大约1.8e19）。 - 分母b的候选值数量有限（不超过20×9=180个），因此枚举高效。