对 x,y 验证等式

Question

我必须构建一个如下所示的程序：

用户输入 3 个整数：a、b、c
用户输入一个整数n，然后n个整数（升序，不同的数字）
如果验证等式 ax^2 + by^2 =，程序将检查输入数字的所有可能对 (x,y)（x!=y） c 并打印验证等式的所有对。

我的程序如下：

#include<iostream>
using namespace std;
int main() {
int a,b,c,n,i,j;
cin >> a;
cin >> b;
cin >> c;
cin >> n;
int num[n];
for(i=0;i<n;i++) {
   cin >> num[i];
}
for (i=0;i<n;i++)
for (j=i+1;j<n;j++) {
    if(a*num[i]*num[i]+b*num[j]*num[j] == c) {
      cout << "(" << num[i] << "," << num[j] << ")";
    }
    if(a*num[j]*num[j]+b*num[i]*num[i] == c) {
      cout << "(" << num[j] << "," << num[i] << ")";
    }
 }
 return 0;
 }

我用两个 'for' 语句用 O(nlogn) 完成了它，但我知道它可以用 O(n) 完成。

请注意，我的程序可以运行，我不需要像您在评论中所说的那样添加预期输出和我的当前输出。我只希望它是 O(N) 而不是 O(nlogn) -> 我想要代码的优化版本！

我该怎么做？

运行程序示例：a=1，b=1，c=20 那么 n = 5 然后n个数：2 3 4 9 18 程序将显示验证方程 x^2 + y^2 = 20 的所有对 (x,y)。在这种情况下它显示 (2,4) 和 (4,2).

谢谢！

Answer 1

假设基于 0 的索引...

Set i=0
Set j=n-1
While i<n or j>=0
    Set sum=a(num[i]^2)+b(num[j^2)
    If sum==c then found pair, and increase i
    If sum<c increase i
    If sum>c decrease j

Answer 2

我发现这个问题在这里得到了解决：http://lonews.ro/educatie-cultura/22899-rezolvare-admitere-universitatea-bucuresti-2015-pregatire-informatica.html 并稍作更改以显示对数（它最初显示对数）。

#include <iostream>
using namespace std;

int main()
{
   int a, b, c, n, i=0;
   cout << "a = ";
   cin >> a;
   cout << "b = ";
   cin >> b;
   cout << "c = ";
   cin >> c;
   cout << "n = ";
   cin >> n;

   int s[n];
   for(i=0; i<n; i++) {
       cout << "s[" << i+1 << "] = ";
       cin >> s[i];
   }
   int j=n-1;
   i = 0;
   while(j>=0 || i<n) {
       if(a*s[i]*s[i] + b*s[j]*s[j] == c) {
           cout << "(" << s[i] << "," << s[j] << ") ";
           i++;
       }
       if(a*s[i]*s[i] + b*s[j]*s[j] < c) {
           i++;
       }
       if(a*s[i]*s[i] + b*s[j]*s[j] > c) {
           j--;
       }
   }
   return 0;
}

对 x,y 验证等式

Pairs x,y verify equation

algorithm

big-o

equation

time-complexity