Решение задачи "Делимость на 7 " с Acmp

С пояснением Просмотров: 78

Требуется определить делимость на 7 ряда целых чисел, записанных в двоичной системе счисления.

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    string s;
    for(int i = 0; i < n; ++i){
        cin >> s;
        int x = 0;
        for(int i = 0; i < s.size(); ++i)
            x = (x * 2 + s[i] - 48) % 7;
        if(x)
            cout << "No";
        else
            cout << "Yes";
        cout << endl;
    }
    return 0;
}

На первый взгляд, задача может показаться достаточно сложной в реализации и многие, возможно, прибегнут к тяжелому решению: переводу длинного двоичного числа в десятичное и многократному делению длинного десятичного на 7; либо к делению длинного двоичного на двоичное 7. В любом из этих случаев не избежать достаточно сложных механизмов реализации длинной арифметики. Причем в данных ограничениях неэффективная реализация может привести к превышению времени выполнения программы.

Используем следующее свойство: число в системе счисления с основанием K делится на K-1 тогда и только тогда, когда сумма цифр данного числа так же делится на K-1. Всем известно, что в десятичной системе число делится на 9 тогда и только тогда, когда сумма его цифр делится на 9. А вышеописанное свойство - это некоторое обобщение известного всем факта. В нашем случае мы можем это использовать. Для этого следует перевести заданное число в 8-ную систему счисления, сложить полученные цифры и проверить делимость на 7 уже обычного числа. Напомним, что каждая тройка цифр двоичного числа представляет отдельную цифру того же числа в 8-ой системе счисления.