首页 > 代码库 > Funky Numbers CodeForces - 192A

Funky Numbers CodeForces - 192A

2024-09-16 16:49:08   217人阅读

As you very well know, this year‘s funkiest numbers are so called triangular numbers (that is, integers that are representable as 技术分享, 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?≤?109).

Output

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

Example

Input
256
Output
YES
Input
512
Output
NO

Note

In the first sample number 技术分享.

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

写得有点丑~~~

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<math.h>
 5 #include<string>
 6 using namespace std;
 7 typedef long long ll;
 8 
 9 int n;
10 ll cal(ll ans){
11    return ans*(ans+1)/2;
12 }
13 
14 int main()
15 {  while(~scanf("%d",&n)){
16        int flag=0;
17        for(int i=1;i<=sqrt(2*n)+1;i++){
18               ll sum=n-cal(i);
19               ll l=i,r=sqrt(2*n)+1;
20               ll mid;
21               while(l<r){
22                     mid=(l+r)/2;
23                     if(cal(mid)==sum){
24                          flag=1;
25                          break;
26                     }
27                     if(cal(mid)<sum) l=mid;
28                     else r=mid;
29                     if(r-l==1){
30                          if(cal(r)==sum||cal(l)==sum){
31                              flag=1;
32                              break;
33                          }
34                          else break;
35                     }
36               }
37               if(flag) break;
38        }
39        if(flag) printf("YES\n");
40        else printf("NO");
41    }
42 }

 

Funky Numbers CodeForces - 192A


联系
我们