Description
經(jīng)過一系列的游戲之后，你終于迎來了今天的作業(yè)，第一個作業(yè)是預(yù)習(xí)一個超級美好的函數(shù)f(x),描述如下。

為了研究這個函數(shù)的性質(zhì)，你決定定義一次變化為x=f(x)。

若x就經(jīng)過若干次變化為k，則你就會覺得這是一個k變變數(shù)。

現(xiàn)在既然你已經(jīng)這么覺得了，那就只好給定A,B,求有多少個A<=x<=B是k變變數(shù)了。

Input
輸入包含三行。

第一行為一個整數(shù)k。

第二行為一個整數(shù)A。

第三行為一個整數(shù)B。

Output
輸出僅一行，表示答案。

Sample Input
Sample Input 1
13
12345
67890123

Sample Input2
1
234567
1234567

Sample Output
Sample Output1
8387584

Sample Output2
1000001

Data Constraint

Hint
對于50%的數(shù)據(jù)，0<=k,A,B<=10^6
對于100%的數(shù)據(jù)，0<=k,A,B<=10^18 A<=B

.
.
.
.
.
分析
對于一個k，我們可以知道，它可以是由2 * k和2 * k+1變化得來的
而2 * k又是由2 * 2*k和2 * 2 * k+1變化得來的
同時2 * k+1又是由2 * (2 * k+1)和2 * (2 * k+1)+1變化得來的
以此類推，我們就可以得到一棵二叉樹
其中，每一層的數(shù)字都是連續(xù)的，樹上的每一個數(shù)字都可以通過變化得出k
利用這個性質(zhì)，我們可以通過判斷每一層有多少個數(shù)字在a~b的范圍內(nèi)從而逐層累加的出答案

然而，當(dāng)k為偶數(shù)時
k不僅能由2 * k和2 * k+1變化得來，同時也能由k+1變化得來
因此，當(dāng)k為偶數(shù)時，答案的統(tǒng)計也應(yīng)該加上k+1的答案

由于任何數(shù)都可以變化得到0、1、2
所以，當(dāng)k=0或1或2時，可以直接輸出答案

要注意k有可能大于a
所以答案的統(tǒng)計范圍為max(a,k)~b

.
.
.
.
.
.
程序：

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std;int main() {long long k,a,b;scanf("%lld",&k);scanf("%lld",&a);scanf("%lld",&b);a=max(k,a);if (k==0||k==1||k==2){printf("%lld",b-a+1);return 0;}long long ans=0,ta=k,tb=k;while (ta<=b){if (ta>=a){if (tb<=b) ans+=tb-ta+1;if (tb>b) ans+=b-ta+1;}if (ta<a){if (tb>b) {ans+=b-a+1;break;}}ta=(long long)ta*2;tb=(long long)tb*2+1;}if (k%2==0){k++;long long ta=k,tb=k;while (ta<=b){if (ta>=a){if (tb<=b) ans+=tb-ta+1;if (tb>b) ans+=b-ta+1;}if (ta<a){if (tb>b) {ans+=b-a+1;break;}}ta=(long long)ta*2;tb=(long long)tb*2+1;}}printf("%lld",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/10458949.html

總結(jié)

以上是生活随笔為你收集整理的超级变变变的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。