Guest User

using binary search

a guest
Jan 7th, 2020
148
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.75 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.    
  8.     long long int n;
  9.     cin>>n;
  10.  
  11.     vector<long long int>ans;
  12.     for(int i=0;i<=60;i++){
  13.         long long int temp = pow(2,i)-1;
  14.         long long int mid,high=1e8,low=0;
  15.  
  16.         while(low<=high){
  17.             mid = (low+high)/2;
  18.             long long int val;
  19.             val = mid-1;
  20.             val = val*mid;
  21.             val = val/2;
  22.             if(temp!=0 && mid>(LLONG_MAX)/(temp)){
  23.                 val = LLONG_MAX;
  24.             }else{
  25.                 val = val+temp*mid;
  26.             }
  27.             if(val==n){
  28.                 if(mid&1){
  29.                     ans.push_back(mid*(temp+1));
  30.                 }
  31.                 break;
  32.             }else if(val<n){
  33.                 low=mid+1;
  34.             }else{
  35.                 high=mid-1;
  36.             }
  37.         }
  38.     }
  39.  
  40.     if(ans.size()==0){
  41.         cout<<"-1"<<endl;
  42.     }else{
  43.         sort(ans.begin(),ans.end());
  44.         for(auto uj:ans){
  45.             cout<<uj<<" ";
  46.         }
  47.         cout<<endl;
  48.     }
  49. }
Add Comment
Please, Sign In to add comment