Hướng dẫn giải của Sum And Mul 2

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: tranxuantruong

Cách 1 Bài này chỉ cần giải hệ phương trình ra, rồi nhập công thức vào code để in kết quả ra là được

Cách 2 Duyệt toàn bộ.

  • Nhìn vào đề bài ta thấy x*x+y*y=B
  • Mà ta thấy B nằm trong khoảng 4e6 (1 số khá nhỏ) --> sqrt(b)=2e3. Vì thể ta chỉ cần duyệt x và y trong khoảng -2e3 đến 2e3 là được. Dùng 2 vòng for lồng nhau như thế độ phức tạp là O(n^2) khá nhỏ cho bài này.
  • Ngoài ra kiểm tra điều kiện khác như x<=y và nếu không có đáp án thì in ra "-1 -1"

Code

#include <bits/stdc++.h>

using namespace std; 

int main(){
    int a; cin >> a; 
    int b; cin >> b; 

    for(int x=-2000; x<=2000; ++x){
        for(int y=x; y<=2000; ++y){
            if(x+y==a && x*x+y*y==b){
                cout <<x <<" " <<y <<endl; 
                return 0; 
            }
        }
    }

    cout <<-1 <<" " <<-1 <<endl; 








    return 0; 
}

Ngoài ra sửa lại vài dòng code thì độ phức tạp là chỉ còn O(n)

#include <bits/stdc++.h>

using namespace std; 

int main(){
    int a; cin >> a; 
    int b; cin >> b; 

    for(int x=-2000; x<=2000; ++x){
        int y=a-x; 

        if(x<=y && x*x+y*y==b){
            cout <<x <<" " <<y <<endl; 
            return 0; 
        }
    }

    cout <<-1 <<" " <<-1 <<endl; 








    return 0; 
}

Bình luận

Hãy đọc nội quy trước khi bình luận.

Không có bình luận tại thời điểm này.