쌍 X, Y는 식

Question

확인 I는 다음과 같은 설정 프로그램을 작성해야한다 :

1. 사용자 3 개 정수 유입 A, B를
2. 다음 사용자가 N의 정수 (오름차순 한 정수 n을 진입 및 C 다른 숫자)
3. 수식 a x^2 + b y^2 = c를 확인하면 입력 한 숫자의 가능한 모든 쌍 (x, y) (x! = y)을 확인하고 방정식을 검증합니다. 나는 다음과 같은 설정 프로그램을 수행

는 :

#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; 
} 

나는 문 '에 대한'두와 O (nlogn)하여 만든하지만 난이 O (n)을 수행 할 수 있습니다 알고있다.

내 프로그램이 작동하며 의견에 명시된대로 예상되는 출력과 현재 출력을 추가하지 않아도된다는 점에 유의하십시오. O (Nlogn)이 아닌 O (N) 만 가능합니다 -> 나는 코드의 최적화 된 버전을 원합니다!

어떻게하면됩니까? 실행하는 프로그램의

예 : A = 1, B = 1, C = 20 그런 N =이어서 5 N 번호 :하는 검증하고 모든 쌍 (X, Y)을 표시한다 2 3 4 9 18 프로그램 이 경우 방정식은 (2,4) 및 (4,2)를 표시합니다.

감사합니다. 0 기반 인덱스를 가정

Answer 1

...

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; 
}