题解：奶牛平方根问题

这道题要求我们找到最小的整数 ( N )，使得 ( \sqrt{N} ) 的小数部分以给定的数字字符串开头。例如，当给定字符串为 "123" 时，最小的 ( N ) 是 17，因为 ( \sqrt{17} \approx 4.1231 )，其小数部分以 "123" 开头。

方法思路

1. 问题转换：

   • 将给定的数字字符串转换为小数范围。例如，字符串 "123" 对应的小数范围是 ( [0.123, 0.124) )。
   • 我们需要找到最小的整数 ( N )，使得 ( \sqrt{N} ) 的小数部分落在这个范围内。

2. 数学推导：

   • 设 ( \sqrt{N} = m + f )，其中 ( m ) 是整数部分，( f ) 是小数部分。
   • 我们需要 ( f ) 满足 ( c \leq f < c + \text{err} )，其中 ( c ) 是给定字符串转换后的小数，( \text{err} = 10^{-L} )。
   • 因此，( N = (m + f)^2 )，我们需要找到最小的 ( m ) 和对应的 ( N )。

3. 算法优化：

   • 从小到大枚举 ( m )，检查是否存在 ( f ) 使得 ( (m + f)^2 ) 是整数，并且 ( f ) 在指定范围内。
   • 当找到第一个满足条件的 ( m ) 时，计算对应的最小 ( N )。

解决代码

#define _CRT_SECURE_NO_WARNINGS
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;

typedef long long LL;

int main()
{
    LL d;
    double n, c, err;
    double f;

    while(cin >> n){
        cin >> d;
        if(d == 0){
            cout << "0" << endl;
            continue;
        }
        c = (double)d / pow(10.0, n);
        err = pow(10.0, -n);
        f = 1;
        while(f < 1000000000){
            if((LL)((f + c) * (f + c)) + 1 < (f + c + err) * (f + c + err)){
                break;
            }
            f = f + 1;
        }
        
        cout << (LL)(ceil((f + c) * (f + c))) <<endl;
    }

    return 0;
}

代码解释

1. 输入处理：

   • 读取整数 ( L ) 和数字字符串 ( d )。
   • 若 ( d ) 为 0，直接输出 0。

2. 范围计算：

   • 将数字字符串转换为小数 ( c )，例如 "123" 转换为 ( 0.123 )。
   • 计算误差范围 ( \text{err} = 10^{-L} )，例如 ( L=3 ) 时，( \text{err} = 0.001 )。

3. 枚举整数部分：

   • 从 ( f = 1 ) 开始枚举可能的整数部分 ( m )。
   • 检查是否存在 ( f ) 使得 ( (m + f)^2 ) 是整数，并且 ( f ) 在 ( [c, c + \text{err}) ) 范围内。

4. 结果计算：

   • 当找到满足条件的 ( m ) 时，计算最小的 ( N ) 为 ( \lceil (m + c)^2 \rceil )。

这种方法通过枚举和数学推导，有效地找到了满足条件的最小整数 ( N )，同时处理了浮点精度问题。