Link Sub: http://www.spoj.com/PTIT/problems/P142SUMA/
Người Gửi: Dương Lee
- Problem:
Một số được gọi là số tam giác nếu nó có dạng k*(k+1) / 2 với k là một số nguyên dương. Nhiệm vụ của bạn là kiểm tra một số có là tổng của 2 số tam giác không, 2 số đó không nhất thiết là phải khác nhau.
Input
Dòng duy nhất là một số nguyên dương n cần kiểm tra (1 <= n <= 10^9).
Output
In ra “YES” nếu số đó thỏa mãn, “NO” trong trường hợp còn lại.
Example:
In ra “YES” nếu số đó thỏa mãn, “NO” trong trường hợp còn lại.
Input
256
Output:
YES
Input
512
Output:
NO
- Solution:
- Tìm tất cả các số là số tam giác <= n; Input
512
Output:
NO
- Nếu một số n là tổng của 2 số tam giác thì: tồn tại một 1 số x là số tam giác sao cho n-x là số tam giác.
-> Vậy với mỗi số số tam giác tìm được ở bước 1 thì chặt nhị phận tìm số tam giác n-x. Nếu tìm được thì in YES không tìm được thì NO.