• + 0 comments

    Another dumb Python3 solution, but at least I did it by myself.

    import math
    from collections import Counter
    
    def main():
        a, b = map(int, input().split())
        llen, lsum = muls(a,b)
        rlen,rsum = xors(a,b)
        lmul = 10**(len(str(b))+1)
        print(lsum*lmul*rlen + llen*rsum)
    
    
    def muls_naive(a,b):
        s = set(x*y for x in range(1,a+1) for y in range(1,b+1))
        return len(s), sum(s)
                 
    def xors_naive(a,b):
        s = set(x^y for x in range(1,a+1) for y in range(1,b+1))
        return len(s), sum(s)
    
    def xors(a,b):
        if b<31:
            s = set(x^y for x in range(1,a+1) for y in range(1,b+1))
            return len(s), sum(s)
        bm  = (b+1)//32
        s = set(x^y for x in range(1, a+1) for y in range(bm*32, b+1))
        rlen, rsum =  len(s), sum(s)
        rsum += bm*32*(bm*32-1)//2 
        rlen += bm*32
        if a == 1:
            rlen -= 1
            rsum -= 1
        return rlen, rsum
    
    
    def parts(lo, hi, limit):
        lst = Counter({1:-1})
        for k in range(lo, hi+1): # build all incl/excl combos
            lst1 = Counter()
            if any(k%i==0 for i in lst if i>1): continue
            for (i,v) in lst.items():
                k1 = i*k//math.gcd(i,k)
                if k1 <= limit: lst1[k1] -= v
            lst.update(lst1)
        del lst[1]
        return lst
                
    def mulsum(lo, hi, k): # multiples of k in range lo..hi
        ilo = (lo-1)//k+ 1
        ihi = hi//k
        lret = ihi - ilo +1
        sret = k * (ilo + ihi) * (lret) // 2
        return lret, sret
    
    def muls_parts(a, b):
        # if b < 50: return muls_naive(a,b)
        lret, sret = b, b*(b+1)//2
        for k in range(2, a+1):
            lo, hi = (k-1)*b + 1, k*b
            pp = parts(k, a, hi)
            for (p,v) in pp.items():
                lp, sp = mulsum(lo, hi, p)
                # print(f'section {k}: [{lo},{hi}]  part ({p},{v}) -> {lp}, {sp}')
                lret += v*lp; sret += v*sp
        return lret, sret
    
    muls = muls_parts
    # xors = xors_naive
    
    main()