时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
Rowdark是一个邪恶的魔法师。在他阅读大巫术师Lich的传记时，他发现一类黑魔法来召唤远古生物，鱼丸。
魔法n能召唤类型i鱼丸当且仅当i能够被表示为x xor n*x对于某个正整数x和固定的n。
Rowdark想知道类型为[L,R]之间的鱼丸有多少种能被魔法n召唤。
输入
输入第一行包含个整数n(1 ≤ n ≤ 107)。
第二行包含两个整数，L, R(0 ≤ L ≤ R ≤ 107)。
输出
一行一个整数表示答案。
样例提示
只有3(1 xor 2), 5(3 xor 6), 6(2 xor 4), 9(7 xor 14), 10(6 xor 12)满足要求。
样例输入
2
1 10
样例输出
5
题目要求L到R区间内能表示成x^(n*x)的数的个数。
显然，枚举L到R再判断是否能表示是不现实的。
于是考虑抓住x，x的范围自然是从0开始，最大是到多少呢？
这又和那个式子相关，x^(n*x)，首先n*x的二进制位数要比x长，所以整体长度是由n*x来决定的。而R是整个的上界，自然n*x的长度不能超过R的长度，这样x的上界就能控制了。
所以枚举x从0，知道n*x的二进制长度超过R，然后将所有的x^(n*x)存进一个set容器，是为了防止出现重复的数字（当然没有证明过是否会重复），最后输出set的size就OK。
代码：
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <algorithm> #include <set> #include <map> #include <queue> #include <string> #define LL long long using namespace std; int n, L, R; set <LL> ans; int getLen(LL k) { int len = 0; if (k == 0) return 1; while (k) { k >>= 1; len++; } return len; } void work() { LL t; ans.clear(); for (LL i = 0;; ++i) { if (getLen(n*i) > getLen(R)) break; t = i^(n*i); if (L <= t && t <= R) ans.insert(t); } printf("%d\n", ans.size()); } int main() { //freopen("test.in", "r", stdin); while (scanf("%d%d%d", &n, &L, &R) != EOF) { work(); } return 0; }