UVALive 7279 Sheldon Numbers （暴力打表）

Sheldon Numbers

题目链接：

http://acm.hust.edu.cn/vjudge/contest/127406#problem/H

Description

According to Sheldon Cooper, the best number is 73. In his own words, “The best number is 73. 73 is the 21st prime number. Its mirror, 37, is the 12th, and its mirror, 21, is the product of multiplying 7 and 3. In binary, 73 is a palindrome: 1001001, which backwards is 1001001. Exactly the same.” Prime numbers are boring stuff, and so are palindromes. On the other hand, the binary representation of 73 is rather remarkable: it’s 1 one followed by 2 zeroes, followed by 1 one, followed by 2 zeros, followed by 1 one. This is an interesting pattern that we can generalize: N ones, followed by M zeros, followed by N ones, followed by M zeros, etc, ending in either N ones or M zeroes. For 73, N is 1, M is 2, and there are 5 runs of equal symbols. With N = 2, M = 1 and 4 runs, we would have the string 110110, which is the binary representation of 54. Acknowledging Sheldon’s powerful insight, let us introduce the concept of a Sheldon number: a positive integer whose binary representation matches the pattern ABABAB . . . ABA or the pattern ABABAB . . . AB, where all the occurrences of A represent a string with N occurrences of the bit 1 and where all the occurrences of B represent a string with M occurrences of the bit 0, with N > 0 and M > 0. Furthermore, in the representation, there must be at least one occurrence of the string A (but the number of occurrences of the string B may be zero). Many important numbers are Sheldon numbers: 1755, the year of the great Lisbon earthquake, 1984, of Orwellian fame, and 2015, the current year! Also, 21, which Sheldon mentions, is a Sheldon number, and so is 42, the answer given by the Deep Thought computer to the Great Question of Life, the Universe and Everything. Clearly, there is an infinite number of Sheldon numbers, but are they more dense or less dense than prime numbers? Your task is to write a program that, given two positive integers, computes the number of Sheldon numbers that exist in the range defined by the given numbers.

Input

The input file contains several test cases, each of them as described below. The input contains one line, with two space separated integer numbers, X and Y . Constraints: 0 ≤ X ≤ Y ≤ 2^63

Output

For each test case, the output contains one line, with one number, representing the number of Sheldon numbers that are greater or equal to X and less or equal to Y . Notes: Explanation of output 1. All numbers between 1 and 10 are Sheldon Numbers. Explanation of output 2. 73 is the only Sheldon number in this range.

Sample Input

1 10 70 75

Sample Output

10 1
##题意：求区间[X,Y]之间有多少个Sheldon Number：其二进制表示满足 ABAB...AB 或 ABAB...ABA 的格式. 其中A为连续n(n>0)个1，B为连续m(n>0)个1.
##题解：一开始尝试打表，并在oeis上找到了序列(不过没公式). 后来换个方向从N和M的角度考虑：对于一个满足条件的二进制串：如果N和M、长度这三个因素都固定了，那么这个串也就固定了. 所以符合条件的串的个数少于 64^3 个. 依次枚举N、M、长度这三个因素并构造符合条件的数，加入set判重. 实际上符合条件的数只有4810个. 注意：题目的右区间2^63超出了longlong范围，这里要用unsigned longlong. (%llu) UVA上的题不要再用I64d了，已经被坑好几回了，老是忘.
##代码： ``` cpp #include #include #include #include #include #include #include #include #include #include #include #define LL unsigned long long #define eps 1e-8 #define maxn 101000 #define mod 100000007 #define inf 0x3f3f3f3f #define mid(a,b) ((a+b)>>1) #define IN freopen("in.txt","r",stdin); using namespace std;

set ans;
void init() {
for(int n=1; n<64; n++) {
for(int m=0; m<64; m++) {
for(int len=1; len<=64; len++) {
if(!((len%(m+n)0) || (len%(m+n)n))) continue;
LL cur = 0;
bool flag = 1;
int i = 0;
while(1) {
if(i >= len) break;

                if(flag) {
                    flag = 0;
                    cur <<= n;
                    i += n;
                    cur += (1LL<<n)-1;
                } else {
                    cur <<= m;
                    flag = 1;
                    i += m;
                }
             }
             ans.insert(cur);
        }
    }
}

}

int main(int argc, char const *argv[])
{
//IN;

init();
int sz = ans.size();
LL l,r;
while(scanf("%llu %llu", &l,&r) != EOF)
{
    int Ans = 0;

    set<LL>::iterator it;
    for(it=ans.begin(); it!=ans.end(); it++) {
        if((*it)>=l && (*it)<=r) {
            Ans++;
            //printf("%d
", *it);
        }
    }
    printf("%d
", Ans);
}

return 0;

}