题目描述给定一个整数nnn2≤n≤1062 \le n \le 10^62≤n≤106和一个二进制字符串SSS长度不超过202020需要在n\sqrt{n}n的二进制表示的小数部分中找到SSS第一次出现的位置。小数部分第一位的位置为000。答案保证不超过100100100。若n\sqrt{n}n为整数则小数部分为无限个000。输入格式第一行包含一个整数TTTT≤100T \le 100T≤100表示测试用例的数量。接下来TTT行每行包含一个整数nnn和一个二进制字符串SSS。输出格式对于每个测试用例输出一行一个整数表示SSS在n\sqrt{n}n二进制小数部分第一次出现的位置。样例输入2 2 101 1202 110011输出2 58题目分析本题的核心是计算n\sqrt{n}n的二进制小数表示并在其中查找子串SSS。一个直观的思路是先计算n\sqrt{n}n的十进制小数再转换为二进制。但十进制转二进制需要高精度运算且题目中nnn最大为10610^6106答案位置不超过100100100这意味着我们只需要计算前120120120位左右的二进制小数即可。直接使用浮点数如double计算会因精度不足而失败因为120120120位二进制小数对应的精度要求远超double的535353位有效数字。因此必须使用高精度整数运算来模拟开平方过程。解题思路手工开平方的原理手工开平方竖式开平方是一种逐位确定平方根的方法。对于十进制每次确定一位小数对于二进制同样适用。本题可以采用二进制直接开平方的思路避免十进制与二进制之间的转换。二进制手工开平方的数学基础设当前已经确定的平方根为yyy二进制表示余数为rn−y2r n - y^2rn−y2。要确定下一位二进制小数b∈{0,1}b \in \{0, 1\}b∈{0,1}我们需要判断(yb2k1)2≤n \left(y \frac{b}{2^{k1}}\right)^2 \le n(y2k1b)2≤n其中kkk是已确定的小数位数。将不等式两边乘以22k22^{2k2}22k2得到(2yb)2≤n⋅4⋅22k (2y b)^2 \le n \cdot 4 \cdot 2^{2k}(2yb)2≤n⋅4⋅22k在实现中我们可以每确定一位就将nnn左移222位相当于乘以444将yyy左移111位然后尝试将最低位设为111计算其平方并与nnn比较。算法流程计算整数部分使用sqrt(n)得到整数部分r⌊n⌋r \lfloor \sqrt{n} \rfloorr⌊n⌋并转为二进制字符串rb。处理完全平方数若r2nr^2 nr2n则n\sqrt{n}n为整数小数部分全为000。直接判断SSS是否全为0并输出000题目保证有解此处直接输出000即可。初始化将nnn转为二进制字符串nb小数部分字符串fb初始为空。逐位确定小数循环120120120次足够覆盖答案范围将nb末尾添加00相当于左移222位。构造候选根rb fb 1。计算候选根的平方高精度二进制乘法。若nb不小于该平方则当前小数位为111否则为000。将确定的位追加到fb末尾。查找子串在fb中查找SSS第一次出现的位置输出结果。高精度运算的实现由于二进制数字的位数最多约120120120位平方后的位数约为240240240位完全可以在string上手动模拟二进制运算比较先比较长度长度相同则按字典序比较。平方模拟二进制竖式乘法使用vectorint暂存中间结果最后转换为string。复杂度分析每个测试用例需要计算120120120位小数。每次迭代需要进行一次二进制平方运算复杂度为O(L2)O(L^2)O(L2)其中LLL为当前二进制数的长度约O(120)O(120)O(120)。总时间复杂度O(T⋅120⋅1202)O(T⋅1.7×106)O(T \cdot 120 \cdot 120^2) O(T \cdot 1.7 \times 10^6)O(T⋅120⋅1202)O(T⋅1.7×106)对于T≤100T \le 100T≤100完全可行。空间复杂度O(L)O(L)O(L)用于存储二进制字符串。代码实现// Searching in sqrt(n)// UVa ID: 12505// Verdict: Accepted// Submission Date: 2026-06-14// UVa Run Time: 0.100s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;boolge(conststringa,conststringb){if(a.length()!b.length())returna.length()b.length();returnab;}stringsquare(conststringa){vectorintr(2*a.length(),0);for(intia.length()-1;i0;i--)for(intja.length()-1;j0;j--){intp(a[i]-0)*(a[j]-0);r[ij1]p;r[ij]r[ij1]1;r[ij1]1;}string s;boolleadtrue;for(intv:r){if(leadv0)continue;leadfalse;schar(v0);}returns.empty()?0:s;}stringbinary(intn){if(n0)return0;string s;while(n){schar((n1)0);n1;}reverse(s.begin(),s.end());returns;}intmain(){intT;cinT;while(T--){intn;string S;cinnS;intr(int)sqrt(n);if(r*rn){cout0\n;continue;}string rbbinary(r),nbbinary(n),fb;for(inti0;i120;i){nb00;if(ge(nb,square(rbfb1)))fb1;elsefb0;}cout(int)fb.find(S)\n;}return0;}总结本题的核心技巧是二进制手工开平方通过高精度整数运算逐位确定平方根的小数部分。关键点如下避免浮点数使用高精度整数模拟二进制运算完全避免精度问题。平方运算的优化只实现平方而非通用乘法简化代码。逐位构造候选根每次尝试将当前根最低位设为111判断其平方是否超过nnn的放大版本。处理完全平方数直接输出000符合题目保证。这种方法不仅适用于本题还可推广到任意精度的平方根计算场景是学习高精度算法的一个良好范例。