SRM546 Div1 Easy(250) KleofasTail - kusano

2進数で考えると、最下位ビットが0なら右シフト、1なら最下位ビットを0にする。なので、Kを尻尾に含むのは、最上位ビットにKがある数。Kが偶数なら、K+1も。

#include <algorithm>
using namespace std;

long long f( long long K, long long A)
{
    if ( A<0 )
        return 0;
    if ( K==0 )
        return A+1;

    long long c = 0;
    int i;
    for ( i=0; (K<<i)+(1LL<<(i+1-K%2))-1<=A; i++ )
        c += 1LL<<(i+1-K%2);
    c += max(0LL,A-(K<<i)+1);

    return c;
}

class KleofasTail{public:
long long countGoodSequences( long long K, long long A, long long B )
{
    return f(K,B)-f(K,A-1);
}};