Hdu 4143

题目链接

好久没有在Hdu水题了，于是乎在无聊之际还是找了一道水题，

但是看完题目之后，明显是个数学题，我还是感觉有点打触的。

因为一直对数学题没有多大信心。

分析了一下，Y^2 = X^2 + n 可以转化为 Y^2 = (X + a)^2

所以：n = a^2 + 2 * a * X ，而且 X > 0

所以 0 < a <= sqrt(n + 1) - 1

由于要求的是最小的 X，所以只要逆序枚举 a 就可以了，

这里复杂度为 O(sqrt(n))，所以可解。

附上代码：

 #include <cmath>

 #include <cstdio>

 typedef long long LL;

 #define min(x, y) ((x) < (y) ? (x) : (y))

 int main() {

     int T, n;

     scanf("%d", &T);

     while (T--) {

         scanf("%d", &n);

         int ans = -; 

         int k = int(sqrt(n + 1.0)) - ;

         for (int i = k; i > ; i--) {

             long long tmp = n - (long long)i * i;

             if (tmp % ( * i))

                 continue;

             else {

                 if (ans == -)

                     ans = tmp / ( * i);

                 else

                     ans = min(ans, tmp / ( * i));

                 break;

             }

         }

         printf("%d\n", ans);

     }

     return ;

 }

巴特西

Hdu 4143

最新文章

热门文章