sweeneyde

Untitled

Mar 28th, 2020
148
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.35 KB | None | 0 0
  1. from itertools import combinations
  2.  
  3. def f(x):
  4.     return min((bin(x*i).count('1'), i) for i in range(1, 100_000, 2))
  5.  
  6. def solve_odd(m):
  7.     assert m & 1
  8.     powers_of_2 = {}
  9.     power = 1
  10.     exp = 0
  11.     while power not in powers_of_2:
  12.         powers_of_2[power] = exp
  13.         power = (power * 2) % m
  14.         exp += 1
  15.     subset = min_sum_to_zero(powers_of_2, m)
  16.     return sorted(map(powers_of_2.get, subset))
  17.  
  18. def value(subset, powers_of_2):
  19.     return sum(1<<powers_of_2[x] for x in subset)
  20.  
  21. def min_sum_to_zero(powers_of_2, m):
  22.     for num_choices in range(1, len(powers_of_2)+1):
  23.         best = None
  24.         best_value = float('inf')
  25.         for subset in combinations(powers_of_2, num_choices):
  26.             if sum(subset) % m == 0:
  27.                 val = value(subset, powers_of_2)
  28.                 if best is None or val < best_value:
  29.                     best = subset
  30.                     best_value = val
  31.         if best is not None:
  32.             return best
  33.  
  34. def exponent_of_2(x):
  35.     s = bin(x)
  36.     return len(s) - len(s.rstrip('0'))
  37.  
  38. def solve(m):
  39.     even = exponent_of_2(m)
  40.     odd = m >> even
  41.     solution = [x + even for x in solve_odd(odd)]
  42.     assert sum(1<<x for x in solution) % m == 0
  43.     return solution
  44.  
  45. def main():
  46.     N = int(input())
  47.     for _ in range(N):
  48.         m = int(input())
  49.         print(*solve(m))
  50.  
  51. main()
Advertisement
Add Comment
Please, Sign In to add comment