Funky Numbers(二分)

最新推荐文章于 2022-10-30 21:25:57 发布

donCoder

最新推荐文章于 2022-10-30 21:25:57 发布

阅读量476

点赞数

分类专栏：蓝桥杯 ACM

本文链接：https://blog.csdn.net/doncoder/article/details/79900313

版权

蓝桥杯同时被 2 个专栏收录

28 篇文章

订阅专栏

ACM

21 篇文章

订阅专栏

本文介绍了一种算法，用于判断一个给定的整数是否可以表示为两个三角形数之和。通过使用二分查找的方法优化了遍历过程，提高了算法效率。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

As you very well know, this year's funkiest numbers are so called triangular numbers (that is, integers that are representable as $\text{[math]}$ , where k is some positive integer), and the coolest numbers are those that are representable as a sum of two triangular numbers.

A well-known hipster Andrew adores everything funky and cool but unfortunately, he isn't good at maths. Given number n, help him define whether this number can be represented by a sum of two triangular numbers (not necessarily different)!

Input

The first input line contains an integer n (1 ≤ n ≤ 10⁹).

Output

Print "YES" (without the quotes), if n can be represented as a sum of two triangular numbers, otherwise print "NO" (without the quotes).

Examples

Input

Output

YES

Input

Output

NO

Note

In the first sample number $\text{[math]}$ .

In the second sample number 512 can not be represented as a sum of two triangular numbers.

两个循环搜索会超时，所以第二个使用二分搜索

#include <iostream>
#include <math.h>
using namespace std;
typedef long long ll;
int main(){
    ll n,i,A,B,mid,r,l;
    cin>>n;
    int flag=0;
    for(i=1;i<sqrt(2*n);i++){
        A=i*(i+1)/2;
        l=i;r=sqrt(2*n);mid=(l+r)/2;
        while(l<=r){
            B=mid*(mid+1)/2;
            if(A+B<n){
                l=mid+1;
                mid=(l+r)/2;
            }
            else if(A+B>n){
                r=mid-1;
                mid=(l+r)/2;
            }
            else{
                flag=1;
                break;
            }
            
        }
        if(flag==1)
            break;
    }
    if(flag==1)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    
    
    return 0;
}