1970 - secventa xor

Enunţ

Fie secvența S(x) care se construiește astfel:

S(1)=x S(n+1)=S(n) XOR [S(n)/2], unde [x] se definește ca parte întreagă din x, iar XOR este operația clasică „sau exclusiv”.

Cerința

Dându-se un număr natural k, aflați numărul de numere naturale x pentru care S(k+1)=S(1)=x este adevărat. Deoarece numărul poate fi foarte mare, afișați rezultatul modulo 1000000007.

Date de intrare

Fișierul de intrare secventa.in se găsește un singur număr natural k.

Date de ieșire

Fișierul de ieșire secventa.out va conține pe prima linie un singur număr – răspunsul problemei modulo 1000000007.

Dacă pentru un număr k există o infinitate de numere x care respectă cerința, se va afișa numărul -1.

Restricții și precizări

• 1 ≤ k ≤ 10^19

Exemplul 1

secventa.in

260

secventa.out

15

Exemplul 2

secventa.in

100000000000000000000

secventa.out

Date de intrare invalide!

Rezolvare

#1970 secventa xor
MOD = 1000000007

def calculate_sequence_term(k, x):
  while k > 0:
    x = x ^ (x // 2)
    k -= 1
  return x

def count_matching_numbers(k):
  count = 0
  for x in range(1, k + 1):
    if calculate_sequence_term(k, x) == x:
      count += 1
  return count % MOD

def verify_input_data(k):
  if not (1 <= k <= 10 ** 19):
    with open("secventa.out", "w") as fout:
      fout.write("Date de intrare invalide!")
    return False
  return True

def main():
  with open("secventa.in", "r") as fin:
    k = int(fin.readline().strip())

  if not verify_input_data(k):
    return

  matching_numbers = count_matching_numbers(k)

  with open("secventa.out", "w") as fout:
    fout.write(str(matching_numbers))

if __name__ == "__main__":
  main()