You are viewing a single comment's thread. Return to all 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()
Seems like cookies are disabled on this browser, please enable them to open this website
HackerRank Number
You are viewing a single comment's thread. Return to all comments →
Another dumb Python3 solution, but at least I did it by myself.