HackerRank Number Theory – HackerRank Number

Challenge: HackerRank Number

Subdomeniu: Number Theory (number-theory)

Scor cont: 80.0 / 80

Submission status: Accepted

Submission score: 1.0

Submission ID: 464746267

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/hackerrank-number/problem

Cerinta

A Hackerrank number is a magic number that can be used to get sudo permissions on the site. We are going to generate a hackerrank number from two integers A & B. Each number has two parts to it - the left (L) & the right side (R).  
 
For eg: for the number 100101, 

+ L could be 100 & R could be 101 (or) 
+ L could be 1 and R could be 00101 and so on.. 

<i>How to generate a hackerrank number?</i>

Let x & y be integers such that,

    (1 <= x <= A & 1 <= y <= B) 

Generate the left part of any hackerrank number (L) by multiplying x and y (i.e) x*y  
and the right part of any hackerrank number (R) by bitwise xor-ing x and y (i.e) x^y

Add leading zeros to R to make length(R) = length(B) + 1. Concatenate both L & R to form the hackerrank number.

Can you find the sum of all possible hackerrank numbers generated by this rule?

**Input format**

Each input contains 2 integers A and B separated by a space. 

**Constraints**

1 <= A <= 30  
1 <= B <= 10<sup>8</sup>

**Output format**

Print the sum of all possible numbers that satisfy the above mentioned property. 

**Sample Input**

    2 4

**Sample Output**

    14502

The left value can be one of  {1 * 1, 1 * 2, 1 * 3, 1 * 4, 2 * 1, 2 * 2, 2 * 3, 2 * 4}   
which is {1,2,3,4,2,4,6,8}  
and the distinct values are {1, 2, 3, 4, 6, 8}

The right value can be one of {1^1,1^2,1^3,1^4,2^1,2^2,2^3,2^4}  
which is {0, 3, 2, 5, 3, 0, 1, 6} 
and the distinct values are {0, 1, 2, 3, 5, 6} 

All the possible value are

    {
    	100, 101, 102, 103, 105, 106,
    	200, 201, 202, 203, 205, 206,
    	300, 301, 302, 303, 305, 306,
    	400, 401, 402, 403, 405, 406,
    	600, 601, 602, 603, 605, 606,
    	800, 801, 802, 803, 805, 806 
    }

S = all the sum of the above = 14502.

Note: Any number can only be added once.

Cod sursa

def gcd(x, y):
    while y != 0:
        (x, y) = (y, x % y)
    return x

def sumProdRef(A, B):
    all = set()
    for x in range(1, A + 1):
        for y in range(1, B + 1):
            all.add(x * y)
    return sum(all), len(all)

def sumXorRef(A, B):
    all = set()
    for x in range(1, A + 1):
        for y in range(1, B + 1):
            all.add(x ^ y)
    return sum(all), len(all)

def sumProdOneDivider(divider, limit):
    count = limit // divider
    return divider * (count + 1) * count // 2, count

def get(result, x, limit):
    items = result.items()[:]
    if x not in result:
        result[x] = 0
    result[x] += 1
    if result[x] == 0:
        del result[x]
    for d, v in items:
        dx = d * x
        if dx > limit:
            continue
        if dx not in result:
            result[dx] = 0
        result[dx] -= v
        if result[dx] == 0:
            del result[dx]
    return result

def getInterval(start, finish, limit):
    result = {}
    for x in range(start, finish):
        items = list(result.items())[:]
        isdiv = False
        for d in range(start, x):
            if x % d == 0:
                isdiv = True
                break
        if isdiv:
            continue
        result[x] = 1
        for d, v in items:
            dx = d * x // gcd(d, x)
            if dx > limit:
                continue
            if dx not in result:
                result[dx] = 0
            result[dx] -= v
            if result[dx] == 0:
                del result[dx]
    return result

def sumProd(A, B):
    all = set()
    s = 0
    l = 0
    for x in range(A, 0, -1):
        process = getInterval(x, A + 1, A * B)
        for d, v in process.items():
            sx0, lx0 = sumProdOneDivider(d, B * (x - 1))
            sx1, lx1 = sumProdOneDivider(d, B * x)
            s += v * (sx1 - sx0)
            l += v * (lx1 - lx0)
    return s, l

def sumXor(A, B):
    if B < 100:
        return sumXorRef(A, B)
    b = B - 100
    s = b * (b + 1) // 2
    l = b + 1
    all = set()
    for x in range(1, A + 1):
        for y in range(b + 1, B + 1):
            xy = x ^ y
            if xy <= b:
                continue
            all.add(xy)
    s += sum(all)
    l += len(all)
    return s, l
        
A, B = map(int, input().split())
prod, nprod = sumProd(A, B)
xor, nxor = sumXor(A, B)
result = prod * nxor * pow(10, len("%d" % B) + 1) + nprod * xor
print(result)