Bài B - Divide by Zero 2017 and Codeforces Round #399 (Div.1+Div.2,combined)

Bài B:
Đề bài:  Ban đầu Sam có một danh sách ban đầu chỉ 1 một mình số n . Sau đó anh ta thực hiện một số thao tác nhất định trên danh sách đó. Mỗi thao tác, Sam phải bỏ đi bất kì phần tử x nào, thỏa mãn x>1, từ danh sách và thêm vào cùng vị trí đó [x/2], x mod 2, [x/2] lần lượt. Anh ấy phải tiếp tục các thao tác này cho đến khi tất cả các phần tử trong danh sách bằng 0 hoặc 1.
 Bây giờ, thầy của Sam muốn đếm số lần xuất hiện của số 1 trong đoạn [l;r]. Sam muốn trở thành master nhưng không may mắn thay anh ta không thể giải quyết vấn đề này. Hãy giúp Sam vượt qua những khó khăn này.
Đầu vào:
+ Dòng đầu tiên chứa 3 số nguyên n,l,r (0<=n<=2^(50),0<=r-l<=10^5,r>=1,l>=1) - phần tử đầu tiên và dãy l và r.
Đầu ra:
+ In ra số lượng số 1 trong đoạn [l;r].
Ví dụ:
Đầu vào:
7 2 5
Đầu ra:
4
//***//
Đầu vào:
10 3 10
Đầu ra:
5.
Chú thích:
+ Xét ví dụ đầu tiên:
[7]-> [3,1,3],[1,1,1,1,3]->[1,1,1,1,1,1,1]->[1,1,1,1,1,1,1].
Các phần tử từ vị trí thứ 2 đến vị trí thứ 5 trong mảng là [1,1,1,1]. Nên số lượng số 1 là 4.
+ Xét ví dụ thứ hai:
[10]-> [1,0,1,1,1,0,1,0,1,0,1,1,1,0,1]
Các phần tử từ vị trí thứ 3 đến vị trí thứ 10 trong danh sách là [1,1,1,0,1,0,1,0]. Số lượng số 1 là 5.
Hướng dẫn:
 Dễ dàng nhận thấy rằng tổng số các phần tử trong danh sách cuối cùng là $2^{[log_{2}(n)]+1-1}$. Vấn đề này có thể được giải quyết bằng việc xác định vị trí từng phần tử trong danh sách và kiểm tra liệu rằng nó có bằng 1 hay không. Phần tử thứ i có thể xác định được bằng O(log n) bằng cách sử dụng hạng mục chia để trị. Câu trả lời là chính là tổng số các số 1 cần tìm.
Độ phức tạp O((r-l+1)*log(n)).
Lời giải:

#include<bits/stdc++.h>
using namespace std;
long long int cnt(long long int temp) //returns the length of final list 
{
  long long int x=1;
  while(temp>1)
  {
    temp/=2;
    x*=2;
  }
  return x;
}
int is_one(long long int pos,long long int target,long long int num)
{ 
  if(num<2)
    return num;
  if(pos+1==2*target)
  {
    return num%2;
  }
  num/=2;
  pos/=2;   
  if(target>pos+1)
      target-=(pos+1);      
  return is_one(pos,target,num);
}
int main()
{
  long long int l,r,n,x,ans=0,i;
  cin>>n>>l>>r;
  x=cnt(n);
  x=2*x-1;
  for(i=l; i<=r; i++)  ans+=is_one(x,i,n);
  cout<<ans<<endl;  
  return 0;
}