Problem:


Score : 900 points

Problem Statement

Nukes has an integer that can be represented as the bitwise OR of one or more integers between A and B (inclusive).
How many possible candidates of the value of Nukes's integer there are?

Constraints

1 ≤ A ≤ B < 2^{60}

A and B are integers.

Input

The input is given from Standard Input in the following format:

A
B

Output

Print the number of possible candidates of the value of Nukes's integer.

Sample Input 1

7
9

Sample Output 1

4

In this case, A=7 and B=9. There are four integers that can be represented as the bitwise OR of a non-empty subset of {7, 8, 9}: 7, 8, 9 and 15.

Sample Input 2

65
98

Sample Output 2

63

Sample Input 3

271828182845904523
314159265358979323

Sample Output 3

68833183630578410



Sample input:
7
9


Sample output:
4

Submission status: Time Limit Exceeded

Solution code:
A=int(input())
B=int(input())
S=[]
times=len(format(A^B,"b"))
for i in range(A,B+1):
  S+=[i]
D=S[:] #Dは基礎集合
SET=set(S)
#for t in range(times):
for i in range(len(S)):
  for j in range(len(D)):
    SET.add(S[i]|D[j])
print(len(SET))

Submission status: Time Limit Exceeded

Solution code:
A=int(input())
B=int(input())
S=[]
times=len(format(A^B,"b"))
for i in range(A,B+1):
  S+=[i]
D=S[:] #Dは基礎集合
SET=set(S)
for t in range(times):
  for i in range(len(S)):
    for j in range(len(D)):
      S+=[S[i]|D[j]]
      SET.add(S[i]|D[j])
print(len(SET))

Submission status: Accepted

Solution code:
def solve(a, b):
    if a == b:
        return 1

    f = 1 << 60
    r = 0
    while f:
        if r == 0 and b & f and a & f == 0:
            r = f
        elif r > 0 and b & f:
            k = f << 1
            break
        f >>= 1
    else:
        k = 1

    a &= r - 1

    if k > a:
        return (r << 1) - a

    return 2 * (r - a) + k


a = int(input())
b = int(input())
print(solve(a, b))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

def calc(A, B):
    if A == B:
        return 1
    for i in range(61, -1, -1):
        if A&(1<<i) and B&(1<<i):
            A ^= 1<<i
            B ^= 1<<i
        if not A&(1<<i) and B&(1<<i):
            break
    
    Bd = B ^ (1<<(B.bit_length())-1)
    BM = ((1<<Bd.bit_length())-1)
    B = B | BM
    C = (1<<(B.bit_length())-1)
    
    res = (B-A+1) + (C-max(BM+1, A))
    return res
A = int(readline())
B = int(readline())
print(calc(A, B))

Submission status: Accepted

Solution code:
a=int(input())
b=int(input())
if a==b:
  print(1)
  exit()
abin=bin(a)[2:]
bbin=bin(b)[2:]
la=len(abin)
lb=len(bbin)
if la==lb:
  while abin[0]==bbin[0]:
    abin=abin[1:]
    bbin=bbin[1:]
  while len(abin)>1 and abin[0]=="0":
    abin=abin[1:]
cbin=bbin[1:]
while cbin and cbin[0]=="0":
  cbin=cbin[1:]
c=2**(len(cbin))-1
a=int(abin,2)
b=int(bbin,2)
lb=len(bbin)
lbnd=2**(lb-1)+c
hbnd=2**(lb-1)+a
if lbnd>=hbnd:
  print(2**lb-a)
else:
  print(2**(lb-1)-a+lbnd-a+1)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from functools import lru_cache

A = int(readline())
B = int(readline())

@lru_cache(None)
def can_make(A,B):
    # [A,B] の元のorで、{B} 以外の方法でBを作れるかどうか。たいていTrue
    if A == B:
        return False
    if B%2 == 0:
        return can_make((A+1)//2,B//2)
    # Bが奇数なら、{B-1,B}が満たす
    return True

@lru_cache(None)
def F(A,B):
    if A==B:
        return 1
    # 偶数の作り方
    ev = F((A+1)//2,B//2)
    # 奇数の作り方
    if A%2==0:
        A += 1
    if B%2 == 1:
        od = F(A//2,B//2)
    else:
        # 上位の桁では基本的にはA//2～B//2が使える。
        # ただし、{B} 以外でないといけない
        od = F(A//2,B//2)
        if not can_make(A//2,B//2):
            od -= 1
    return ev + od

answer = F(A,B)
print(answer)

Submission status: Accepted

Solution code:
a = int(input())
b = int(input())

if a == b:
    print(1)
    exit()

# 二進数xの長さを求める時、len(bin(x)) - 2　では、xが0のとき1を返してしまい、バグる原因になる
# よって、二進数の長さを計算する関数を用意しておく
def bitlen(x):
    return 1 + bitlen(x >> 1) if x else 0

t = a ^ b
n = bitlen(t)

T = 1 << (n - 1)

a = a & (T * 2 - 1)
b = b & (T * 2 - 1)

sb = b & (T - 1)
b_max = (2 ** bitlen(sb) - 1) | T

if (T + a) > b_max:
    print((b_max - a + 1) + (2 * T - 1 - (T + a) + 1))
else:
    print(2 * T - 1 - a + 1)

Submission status: Accepted

Solution code:
a=bin(input()+(1<<60))[2:]
b=bin(input()+(1<<60))[2:]
if a==b:
	print 1
	exit()
while a[0]==b[0]:
	a=a[1:]
	b=b[1:]
assert a[0]=="0" and b[0]=="1"
result=int("1"+"0"*(len(a)-1), 2)-int(a, 2)
b=b[1:]
while b and b[0]=="0":
	b=b[1:]
if not b:
	b=0
else:
	b=(1<<len(b))-1
if b>=int(a, 2):
	result+=(1<<(len(a)-1))
else:
	result=result*2+b+1
print result

Submission status: Accepted

Solution code:
l = int(raw_input())
r = int(raw_input())
if l == r:
	print 1
	exit(0)
k = l ^ r
while k != (k & -k):
	k ^= k & -k
l &= (k << 1) - 1
r &= k - 1
while r != (r & -r):
	r ^= r & -r
r = r * 2 - 1 if r else 0
print 2 * k - l if r >= l else (k - l << 1) + r + 1

Submission status: Accepted

Solution code:

import math
A = int(input())
B = int(input())
if B < A: A,B = B,A

if A == B:
    print(1)
else:
    t = int(math.floor(math.log2(B)))
    while (A & 2**t) == (B & 2**t):
        if A & 2**t:
            A -= 2**t
            B -= 2**t
        t-=1
    ans = 2**t - A              # [A,2^t-1]
    r = t-1
    while 2**t + 2**r > B and r>=0:
        r-=1
    # [2^t,2^t+2^{r+1}-1] \cup [2^t+A,2^{t+1}-1]
    C = 2**(r+1)
    if C < A:
        ans += C + 2**t - A
    else:
        ans += 2**t
    print(ans)

Submission status: Accepted

Solution code:
a,b=int(input()),int(input())
if a==b:
	print(1)
else:
	r=60
	while (a&(1<<r))==(b&(1<<r)):
		r-=1
	t=(1<<(r+1))
	a&=t-1
	b&=t-1
	k=r-1
	while k>=0 and (b&(1<<k))==0:
		k-=1
	ans=t-a
	if a>(1<<(k+1)):
		ans-=a-(1<<(k+1))
	print(ans)

Submission status: Accepted

Solution code:
import fileinput

iterator = fileinput.input()

a = int(iterator.next())
b = int(iterator.next())

def compute(a, b):
    if a == b:
        return 1

    # remove prefix
    n = (a ^ b).bit_length()
    high_order_bit = 1 << (n-1)
    ones_mask = (high_order_bit << 1) - 1
    a = a & ones_mask
    b = b & ones_mask

    # count possibilities
    # with first prefix 0
    prefix_0_count = high_order_bit - a
    # with first prefix 1
    b_max = (1 << (b ^ high_order_bit).bit_length()) - 1
    if a > b_max:
        prefix_1_count = b_max + 1 + prefix_0_count
    else:
        prefix_1_count = high_order_bit

    return prefix_0_count + prefix_1_count

print compute(a, b)

Submission status: Accepted

Solution code:
import sys

def solve():
    a = int(input())
    b = int(input())

    if a == b:
        print(1)
        return

    t = a ^ b
    N = bitlen(t)

    a = a & (2**N - 1)
    b = b & (2**N - 1)

    blen = bitlen(b)

    sb = b & (2**(blen - 1) - 1)

    sblen = bitlen(sb)

    s = 2**sblen - 1

    ymax = b | s

    T = 2**(N - 1)

    ans = T - a

    if ymax < T + a:
        ans += ymax + 1 - a
    else:
        ans += T

    print(ans)

def bitlen(x):
    return 1 + bitlen(x >> 1) if x else 0

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys

def solve():
    a = int(input())
    b = int(input())

    if a == b:
        print(1)
        return

    t = a ^ b
    N = len(bin(t)) - 2
    t = 1 << N

    a = a & (t - 1)
    b = b & (t - 1)

    blen = len(bin(b)) - 2

    sb = b & (2**(blen - 1) - 1)

    if sb == 0:
        sblen = 0
    else:
        sblen = len(bin(sb)) - 2

    s = (1<<sblen) - 1

    ymax = b | s

    T = 1<<(N - 1)

    ans = T - a

    if ymax < T + a:
        ans += ymax - T + 1 + T - a
    else:
        ans += T

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
a = int(raw_input())
b = int(raw_input())
def f(l, h, i):
    if i == 0:
        return h - l + 1
    t = (1 << i)
    if h < t:
        return f(l, h, i - 1)
    if l >= t:
        return f(l - t, h - t, i - 1)
    k = f(0, h - t, i - 1)
    if k >= l:
        return t - l + t
    else:
        return (t - l) * 2 + k
    return res
print f(a, b, 60)

Submission status: Accepted

Solution code:
# D
res = 0

A = int(input())
B = int(input())

def pow2_floor_log2(x):
    res = 1
    while res*2 <= x:
        res *= 2
    return res

if A == B:
    res += 1
    
while A < B:
    # find log2A and log2B
    C = pow2_floor_log2(B)
    if A < C:
        # A to C
        res += C - A
        if B > C:
            B_ = C + pow2_floor_log2(B - C)*2 - 1
        else:
            B_ = C
        if C + A <= B_:
            res += C
            break
        else:
            res += (C - A) + (B_ - C + 1)
            break
    else:
        A -= C
        B -= C

print(res)

Submission status: Runtime Error

Solution code:
a=int(input())
b=int(input())
if a==b:
  print(1)
  exit()
abin=bin(a)[2:]
bbin=bin(b)[2:]
la=len(abin)
lb=len(bbin)
if la==lb:
  while abin[0]==bbin[0]:
    abin=abin[1:]
    bbin=bbin[1:]
  while abin[0]=="0":
    abin=abin[1:]
cbin=bbin[1:]
while cbin[0]=="0":
  cbin=cbin[1:]
c=2**(len(cbin))-1
a=int(abin,2)
b=int(bbin,2)
lb=len(bbin)
lbnd=2**(lb-1)+c
hbnd=2**(lb-1)+a
if lbnd>=hbnd:
  print(2**lb-a)
else:
  print(2**(lb-1)-a+lbnd-a+1)

Submission status: Runtime Error

Solution code:
a=int(input())
b=int(input())
if a==b:
  print(1)
  exit()
abin=bin(a)[2:]
bbin=bin(b)[2:]
la=len(abin)
lb=len(bbin)
if la==lb:
  while abin[0]==bbin[0]:
    abin=abin[1:]
    bbin=bbin[1:]
  while abin[0]=="0":
    abin=abin[1:]
cbin=bbin[1:]
while cbin[0]=="0":
  cbin=cbin[1:]
c=2**(len(cbin))
a=int(abin,2)
lbnd=2**(lb-1)+c
hbnd=2**(lb-1)+a
if lbnd>=hbnd:
  print(2**(lb-1)-a)
else:
  print(2**(lb-1)-a+lbnd-a)

Submission status: Runtime Error

Solution code:
a=int(input())
b=int(input())
if a==b:
  print(1)
  exit()
abin=bin(a)[2:]
bbin=bin(b)[2:]
la=len(abin)
lb=len(bbin)
if la==lb:
  while abin[0]==bbin[0]:
    abin=abin[1:]
    bbin=bbin[1:]
  while abin[0]=="0":
    abin=abin[1:]
cbin=bbin[1:]
while cbin[0]=="0":
  cbin=cbin[1:]
c=2**(len(cbin))
a=int(abin,2)
lbnd=2**(lb-1)+c
hbnd=2**(lb-1)+a
if lbnd>=hbnd:
  print(lbnd-a+1)
else:
  print(2**(lb-1)-a+lbnd-a+1)

Submission status: Runtime Error

Solution code:
a=int(input())
b=int(input())
if a==b:
  print(1)
  exit()
abin=bin(a)[2:]
bbin=bin(b)[2:]
la=len(abin)
lb=len(bbin)
if la==lb:
  while abin[0]==bbin[0]:
    del abin[0]
    del bbin[0]
  while abin[0]=="0":
    del abin[0]
cbin=bbin[1:]
while cbin[0]=="0":
  del cbin[0]
c=2**(len(cbin))
a=int(abin,2)
lbnd=2**(lb-1)+c
hbnd=2**(lb-1)+a
if lbnd>=hbnd:
  print(lbnd-a+1)
else:
  print(2**(lb-1)-a+lbnd-a+1)

Submission status: Runtime Error

Solution code:
#include <stdio.h>
#include <math.h>
#include <algorithm>
long long a, b;
int main()
{
    scanf("%lld%lld", &a, &b);
    if (a == b)return !puts("1");
    int _ = 60;
    while (~(-- _))
        if ((a & (1ll << _)) ^ (b & (1ll << _)))
        {
            a &= (1ll << (_ + 1)) - 1, b &= (1ll << (_ + 1)) - 1;
            long long __ = 1ll << (int)(log2(b & ((1ll << _) - 1)));
            __ = (!__)? 1ll: __ << 1;
            return !printf("%lld\n", (1ll << (_ + 1)) - a + std :: min(0ll, __ - a));
        }
    return 0;
}

Submission status: Runtime Error

Solution code:
#include <stdio.h>
#include <math.h>
#include <algorithm>
long long a, b;
int main()
{
    scanf("%lld%lld", &a, &b);
    if (a == b)return !puts("1");
    int _ = 60;
    while (~(-- _))
        if ((a & (1ll << _)) ^ (b & (1ll << _)))
        {
            a &= (1ll << (_ + 1)) - 1, b &= (1ll << (_ + 1)) - 1;
            long long __ = 1ll << (int)(log2(b & ((1 << _) - 1)));
            __ = (!__)? 1ll: __ << 1;
            return !printf("%lld\n", (1ll << (_ + 1)) - a + std :: min(0ll, __ - a));
        }
    return 0;
}

Submission status: Runtime Error

Solution code:
n,a,b=map(int,input().split())
if b<a:
    print(0)
elif n==1 and a!=b:
    print(0)
else:
    A=a*(n-1)+b
    B=a+b*(n-1)
    print(B-A+1)

Submission status: Runtime Error

Solution code:
a=bin(input()+(1<<60))[2:]
b=bin(input()+(1<<60))[2:]
while a[0]==b[0]:
	a=a[1:]
	b=b[1:]
assert a[0]=="0" and b[0]=="1"
result=int("1"+"0"*(len(a)-1), 2)-int(a, 2)
b=b[1:]
while b and b[0]=="0":
	b=b[1:]
if not b:
	result=result*2+1
else:
	b="1"*len(b)
	if int(b, 2)>=int(a, 2):
		result+=(1<<(len(a)-1))
	else:
		result=result*2+int(b, 2)+1
print result

Submission status: Runtime Error

Solution code:
import math
A = int(input())
B = int(input())
if B < A: A,B = B,A

if A == B:
    print(1)
else:
    t = int(math.floor(math.log2(B)))
    while (A & 2**t) == (B & 2**t):
        if A & 2**t:
            A -= 2**t
            B -= 2**t
        t-=1
    ans = 2**t - A              # [A,2^t-1]
    r = t-1
    while 2**t + 2**r > B:
        r-=1
    # [2^t,2^t+2^{r+1}-1] \cup [2^t+A,2^{t+1}-1]
    C = 2**(r+1)
    if C < A:
        ans += C + 2**t - A
    else:
        ans += 2**t

print(ans)

Submission status: Runtime Error

Solution code:
A = int(raw_input())
B = int(raw_input())
ans = 0
bin_A = bin(A)[2:]
bin_B = bin(B)[2:]
bin_A = bin_A.zfill(len(bin_B))
x1 = None
x2 = None
for i in range(len(bin_A)):
    if x1 is None and bin_A[i] != bin_B[i]:
        x1 = len(bin_A)-i
    elif x1 is not None and x2 is None and bin_B[i]=='1':
        x2 = len(bin_A)-i
        break
print (pow(2,x1)-A%(pow(2,x1)))-max(0,(pow(2,x1-1)+A%(pow(2,x1)))-(pow(2,x1-1)+pow(2,x2)))

Submission status: Runtime Error

Solution code:
A = int(input())
B = int(input())

binA = bin(A)[2:]
binB = bin(B)[2:]

#print("A: {0}\nB: {1}".format(binA, binB))
if A == B:
    print(1)

elif len(binB) - len(binA) > 1:
    maxnum = int("1" * len(binB), 2)
    print(maxnum - A + 1)

elif len(binB) - len(binA) == 1:
    res = 2 * (int("1" * len(binA), 2) - A + 1)
    #print("res(temp): {}".format(res))
    for i in range(1, len(binB)):
        if binB[i] == "0":
            continue
        else:
            res += 2 ** (len(binB) - i)

            break
    else:
        res += 1
    print(res)

else:
    same_num = 0
    for i in range(len(A)):
        if binA[i] != binB[i]:
            same_num = i - 1
            break

    res = int(binA[0:same_num] + "0" * (len(binA) - same_num - 1), 2) - A
    #print("res(temp): {}".format(res))
    for i in range(same_num + 1, len(binB)):
        if binB[i] == 0:
            continue
        else:
            res += 2 ** (len(binB) - i - sam_num)
            break
    print(res)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
import math


def main():
    a = int(input())
    b = int(input())
    if a == b:
        print(1)
        return

    # 作れる数字は、高々2**k - 1 (k: floor(log2(b))+1)

    da = math.floor(math.log2(a)) + 1
    db = math.floor(math.log2(b)) + 1
    sys.stderr.write("da: {} db: {}\n".format(da, db))

    if da == db:
        for i in range(da):
            pw = 2**(da - i - 1)
            if a >= pw:
                a -= pw
                b -= pw
                sys.stderr.write("a: {:b} b: {:b}\n".format(a, b))
            elif b >= pw:
                break
        da = math.floor(math.log2(a)) + 1
        db = math.floor(math.log2(b)) + 1
        sys.stderr.write("da: {} db: {}\n".format(da, db))

    # A: a .. (2**k')-1 [k': da - 1]
    total = 2**(db-1) - a
    sys.stderr.write("ta: {}\n".format(total))
    # B: 2**k' + ...
    # B1: 0 .. b
    tb1 = 1
    b_bin = "{:b}".format(b)
    for i in range(1, len(b_bin)):
        if int(b_bin[i]) == 1:
            tb1 = 2**(db - i)
            break
    sys.stderr.write("tb1: {}\n".format(tb1))
    # B2: a .. (11..1)
    tb2 = total
    sys.stderr.write("tb2: {}\n".format(tb2))
    tb = min(tb1 + tb2, 2**(db-1))
    sys.stderr.write("tb: {}\n".format(tb))
    total += tb
    print(total)


main()

Submission status: Runtime Error

Solution code:
# D
res = 0

A = int(input())
B = int(input())

def pow2_floor_log2(x):
    res = 1
    while res*2 <= x:
        res *= 2
    return res


while True:
    # find log2A and log2B
    C = pow2_floor_log2(B)
    if A < C:
        # A to C
        res += C - A
        if B > C:
            B_ = C + pow2_floor_log2(B - C)*2 - 1
        if C + A <= B_:
            res += C
            break
        else:
            res += (C - A) + (B_ - C + 1)
            break
    else:
        A -= C
        B -= C

print(res)

Submission status: Runtime Error

Solution code:
# D
import math
res = 0

A = int(input())
B = int(input())


while True:
    # find log2A and log2B
    C = 2**math.floor(math.log2(B))
    if A < C:
        # A to C
        res += C - A
        if B > C:
            B_ = C + 2**math.floor(math.log2(B - C) + 1) - 1
        if C + A <= B_:
            res += C
            break
        else:
            res += (C - A) + (B_ - C + 1)
            break
    else:
        A -= C
        B -= C

print(res)