Jon fought bravely to rescue the wildlings who were attacked by the white-walkers at Hardhome. On his arrival, Sam tells him that he wants to go to Oldtown to train at the Citadel to become a maester, so he can return and take the deceased Aemon's place as maester of Castle Black. Jon agrees to Sam's proposal and Sam sets off his journey to the Citadel. However becoming a trainee at the Citadel is not a cakewalk and hence the maesters at the Citadel gave Sam a problem to test his eligibility.
Initially Sam has a list with a single element n. Then he has to perform certain operations on this list. In each operation Sam must remove any element x, such that x > 1, from the list and insert at the same position 
, 
, sequentially. He must continue with these operations until all the elements in the list are either 0 or 1.
Now the masters want the total number of 1s in the range l to r (1-indexed). Sam wants to become a maester but unfortunately he cannot solve this problem. Can you help Sam to pass the eligibility test?
The first line contains three integers n, l, r (0 ≤ n < 250, 0 ≤ r - l ≤ 105, r ≥ 1, l ≥ 1) – initial element and the range l to r.
It is guaranteed that r is not greater than the length of the final list.
Output the total number of 1s in the range l to r in the final sequence.
7 2 5
4
10 3 10
5
Consider first example:
Elements on positions from 2-nd to 5-th in list is [1, 1, 1, 1]. The number of ones is 4.
For the second example:
Elements on positions from 3-rd to 10-th in list is [1, 1, 1, 0, 1, 0, 1, 0]. The number of ones is 5.
解题思路：
1、模拟过程，把每次中间的数对二取余的余数计算出来
2、由规律可知其每隔2 、4 、8 、16 分别对应其余数
3、暴力l ->r 计算出其是0还是1
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define MOD 1000000007
#define cinq ios::sync_with_stdio(false)
#define pb push_back
#define mp make_pair
//#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
const int N = 1e7+5;
typedef struct node{
int x;
int y;
int step;
}NODE;
void initt()
{
}
ll n,l,r;
vi a,b;
ll ans[100005];
int main()
{
cinq;
cin >>n>>l>>r;
if(n==0)
{
cout << 0<<endl;
return 0;
}
else if(n==1)
{
cout << 1<<endl;
return 0;
}
for(int i=1;i<100005;i++)
ans[i]=1;
ll t =n;
while(t)
{
b.push_back(t%2);
t/=2;
}
for(int i=b.size()-2;i>=0;i--)
{
a.push_back(b[i]);
}
ll re = 0;
ll tt = 1;
for(ll k=0;;k++)
{
tt *= 2;
if(tt>r) break;
for(ll i=l;i<=r;i++)
{
if(i%tt==0)
ans[i-l+1] = a[k];
}
}
for(ll i=l;i<=r;i++)
{
// cout << ans[i-l+1]<<endl;
re += ans[i-l+1];
}
cout <<re<<endl;
return 0;
}