题目

    

Description

经过一系列的游戏之后，你终于迎来了今天的作业，第一个作业是预习一个超级美好的函数f(x),描述如下。

 

为了研究这个函数的性质，你决定定义一次变化为x=f(x)。

若x就经过若干次变化为k，则你就会觉得这是一个k变变数。

现在既然你已经这么觉得了，那就只好给定A,B,求有多少个A<=x<=B是k变变数了。

 

 

Input

输入包含三行。

第一行为一个整数k。

第二行为一个整数A。

第三行为一个整数B。

 

Output

   输出仅一行，表示答案。

 

 

Sample Input

Sample Input 1131234567890123Sample Input212345671234567

Sample Output

Sample Output18387584Sample Output21000001  

Data Constraint

   

Hint

 对于50%的数据，0<=k,A,B<=10^6

对于100%的数据，0<=k,A,B<=10^18  A<=B

分析

首先，一眼看去，可以暴力，50%是稳的，再加特判，60到手那么，正解是什么?对于个数k，来讲能得到它的只有2*k，2*k+1那么2*k 我们又能得到4*k，4*k+12*k+1 可以得到 4*k+2,4*k+3我们接着慢慢地推导，就可以发现.....显然是棵完全二叉树对于奇数节点是 1,2,4,8,16,32,64,128...对于偶数节点是2,4,8,16,31,64,128...所以我们就可以用一个while，不断乘以2，查找区间范围  p  s：（有可能超出或小于）最后得到答案

代码

 

1 #include<iostream> 2 #define ll long long 3 using namespace std; 4 ll ksm(ll a,ll b) 5 { 6 ll ans=1,x=a; 7 while (b) 8 { 9 if (b&1!=0) ans*=x; 10 x*=x; 11 b>>=1; 12 } 13 return ans; 14 } 15 int main () 16 { 17 ll k,a,b,cs=0,ans=0; 18 cin>>k>>a>>b; 19 if (k==0) 20 { 21 cout<<b-a+1; 22 return 0; 23 } 24 if (k==1) 25 { 26 cout<<b-a+1; 27 return 0; 28 } 29 if (k==2) 30 { 31 if (a==0||a==1) a=2; 32 cout<<b-a+1; 33 return 0; 34 } 35 ll kk=k; 36 ll mi=0; 37 if (k%2==0) 38 cs++; 39 while (kk+mi<a) 40 { 41 kk*=2; 42 cs++; 43 mi=ksm(2,cs); 44 } 45 46 mi=ksm(2,cs); 47 if (a<=kk&&kk+mi-1<=b) 48 ans+=mi; 49 if (a<=kk&&kk+mi-1>b&&kk<=b) 50 ans+=b-kk+1; 51 if (a>kk&&kk+mi-1<=b) 52 ans+=(kk+mi-a); 53 if (a>kk&&kk+mi-1>b) 54 ans+=mi-(a-kk)-(kk+mi-b-1); 55 while (kk<=b*2) 56 { 57 mi*=2; 58 kk*=2; 59 if (a<=kk&&kk+mi-1<=b) 60 ans+=mi; 61 if (a<=kk&&kk+mi-1>b&&kk<=b) 62 ans+=b-kk+1; 63 if (a>kk&&kk+mi-1<=b) 64 ans+=mi-(a-kk); 65 if (a>kk&&kk+mi-1>b) 66 ans+=mi-(a-kk)-(kk+mi-b-1); 67 } 68 cout<<ans; 69 }

 

 

 

 

转载于:https://www.cnblogs.com/zjzjzj/p/10311749.html