【数学】JZOJ_3084 超级变变变

题意

定义函数$f(x)$为：
若$x$为偶数，$f(x)=x/2$；
若$x$为奇数，$f(x)=x-1$。
如果数$x$在变化过程中$(x=f(x))$出现$x=k$，那么我们把$x$叫做$k$变变数，求出区间$l\sim r$中$k$变变数的个数。

思路

其实$f(x)=\lfloor x/2\rfloor$，那么如果 2 n k + x 2^nk+x 2nk+x为变变数，满足
⌊ 2 n k + x 2 n ⌋ = k \left \lfloor \frac{2^nk+x}{2^n} \right \rfloor=k ⌊2n2nk+x​⌋=k
显然是 x < 2 n x<2^n x<2n的，我们就可以枚举$x$，那么每次可以贡献的答案数量就为 2 n 2^n 2n。
如果$k$为偶数，我们还有$x+1$转换过来的情况，所以答案要$\ast 2$。

代码

#includelong long k, a, b;long long ask(long long n) {if (k <= 1) return n;long long g = 1, ans = 0;while (g * k <= n) {ans += g;if (g * k + g - 1 > n) ans -= g * k + g - 1 - n;//范围内g *= 2;}if (!(k & 1)) ans *= 2;return ans;
}int main() {scanf("%lld %lld %lld", &k, &a, &b);printf("%lld", ask(b) - ask(a - 1));
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！