Anonymous Anonymous - 7 days ago
64 0

Известно, что двоичное число состоит из А единиц и B нулей.
Можно ли с уверенность сказать, что некоторое составленное из этих чисел двоичное число делится на N без остатка?

Например, 7 единиц и 2 нуля, делится ли на 25? Можно составить число 101110111 (375), оно делится на 25.

Javascript

Does_binary_number_of_A_set_bits_divide_by_N

const checker = (A, B, N ) => {
  const AB = A+B;
  const P = Array.from(Array(AB), (e, i) => Math.pow(2, i));

  const C = Math.pow(2, A + B) - Math.pow(2, B);
  const D = Math.floor(C / N);
  let k = 0;

  const isSum = K => {
    let cnt = 0;
    for (let j=0; P[j]<K; j++) {
      if ((K & P[j]) > 0) {
        cnt++;
        if (cnt > A) return false;
      }
    }
    return cnt === A;
  }

  const check = () => {
    for (let i=1; i<=D; i++) {
      k += N;
      if (isSum(k)) return k;
    }
    return false;
  }

  return check();
}

console.log(checker(7, 2, 25));
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download