UVA11428 Cubes【数学+二分】

Given a positive integer N you will have to find two positive integers x and y such that:
N = x^3 ? y^3
Input
The input file contains at most 100 lines of inputs. Each line contains a positive integer N (0 < N ≤ 10000). Input is terminated by a line containing a single zero. This line should not be processed.
Output
For each line of input produce one or more lines of output. Each of these lines contains two positive integers x, y separated by a single space, such that N = x^3 ? y^3. If there is no such integer values of x and y then produce the line ‘No solution’ instead. If there is more than one solution then output the one with smallest value of y.
Sample Input
7
37
12
0
Sample Output
2 1
4 3
No solution

问题链接：UVA11428 Cubes
问题简述：（略）
问题分析：
????根据题意可知x,y>0，x>y，x^3=N+y^3。若y>=60则不能满足x>y的条件，矛盾。所以枚举y的时候，只需要考虑0<y<60。先枚举y，然后用二分法查找满足条件的x即可，考虑0<N<=10000，那么y<=x<=y+10000。考虑N=x^3-y^3=(x-y)(xx+xy+yy)进行相关的计算和判定。
????另外一种数学的解法也在这里给出。
程序说明：（略）
参考链接：（略）
题记：（略）

AC的C++语言程序如下：

/* UVA11428 Cubes */

#include <iostream>

using namespace std;

int binary_search(int n, int y) {
    long long l = y, r = y + 10000, mid, k;
    while (l <= r) {
        mid = (l + r) / 2;
        k = (mid - y) * (mid * mid + mid * y + y * y);
        if (k == n) return mid;
        else if (k < n) l = mid + 1;
        else if (k > n) r = mid - 1;
    }
    return 0;
}

int main()
{
    int n, x, y;
    while(~scanf("%d", &n) && n) {
        for(y = 1; y < 60; y++) {
            x = binary_search(n, y);
            if(x) {
                printf("%d %d\n", x, y);
                break;
            }
        }
        if(x == 0)
            printf("No solution\n");
    }

    return 0;
}

AC的C++语言程序如下：

/* UVA11428 Cubes */

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, flag;
    float x, y, minx, miny;
    while(~scanf("%d", &n) && n) {
      flag = 0;
      miny = 1000;
      for(int d = 1; d <= n / 2 + 1; d++) {
          if(n % d == 0) {
              if((12 * n / d - 3 * d * d) < 0) continue;

              x = (-3 * d + sqrt(12 * n / d - 3 * d * d)) / 6;
              y = -(-3 * d - sqrt(12 * n / d - 3 * d * d)) / 6;

              if(x <= 0 || y <= 0) continue;

              if(x == floor(x)) {
                  flag = 1;
                  if(miny > y)  {
                    miny = y;
                    minx = x;
                  }
              }
          }
      }
      if(!flag)
          printf("No solution\n");
      else
          printf("%d %d\n",(int)miny,(int)minx);
    }

    return 0;
}

UVA11428 Cubes【数学+二分】

原文：https://www.cnblogs.com/tigerisland45/p/10368107.html