Question

Помогите написать задачу на с++ Хулиганы Первый и Второй очень не любят доску почёта своей школы. Поэтому они решили наглым образом украсть оттуда школьную стенгазету, сделанную отличниками, и порвать на части. Первый хулиган брал кусочек газеты и рвал его на 4 части, а Второй хулиган – на 7. Однако очень скоро дежурные нашли N кусочков этой газеты. Им стало интересно, все ли кусочки они нашли. Помогите им. Дежурные так старались, что упустить из виду они могли не более 2 кусочков.Входные данные            Натуральное число N < 1018.Выходные данные            Выведите “Yes”, если все кусочки найдены, и “No” – в противном случае.ПримерВход Выход4       Yes 67       Yes 11       No

Answer 1

Вот, правда немного запутано - не стал задумываться об элегантности кода. Алгоритм, вроде как, нашёл (N-1/b). 

#include <iostream>
using namespace std;
int main()
{
int n, b=3, x;
start:
setlocale (LC_ALL, "Russian");
cout << "Введите число собранных кусочков: ";
cin >> n;
x=n-1;
if (x%b==0)
cout << "Yes" << endl;
else
cout << "No" << endl;
goto start;
system ("pause");
}

Answer 2

Для решения этой задачи, мы можем воспользоваться китайской теоремой об остатках (КТО). В данной задаче у нас есть два остатка: один от деления N на 4 и другой от деления N на 7. Мы должны проверить, можно ли восстановить N по этим остаткам и удовлетворить условию "упустить из виду не более 2 кусочков". Если это возможно, то мы выводим "Yes", иначе "No".

Чтобы решить эту задачу, мы можем использовать расширенный алгоритм Евклида для нахождения обратного элемента по модулю. В данном случае, нам нужно найти обратный элемент по модулю 7 и по модулю 4.

1. Вычислим обратный элемент по модулю 7 для остатка от деления N на 4. Пусть x1 - это обратный элемент, тогда: x1 ≡ 4^(-1) mod 7

2. Вычислим обратный элемент по модулю 4 для остатка от деления N на 7. Пусть x2 - это обратный элемент, тогда: x2 ≡ 7^(-1) mod 4

3. Теперь мы можем использовать КТО для восстановления N: N ≡ (4 * x1 * (N % 7) + 7 * x2 * (N % 4)) mod (4 * 7)

4. Если N равно исходному числу N, и условие "упустить из виду не более 2 кусочков" выполняется, то выводим "Yes". В противном случае выводим "No".

Пример реализации на языке C++:

#include

long long mod_inverse(long long a, long long m) {
    // Расширенный алгоритм Евклида для нахождения обратного элемента
    long long m0 = m, t, q;
    long long x0 = 0, x1 = 1;

if (m == 1) return 0;

while (a > 1) {
        // q - частное, t - временная переменная
        q = a / m;
        t = m;

// m - остаток, a - делитель
        m = a % m, a = t;
        t = x0;

// Вычисляем новое значение x0
        x0 = x1 - q * x0;
        x1 = t;
    }

if (x1 < 0) x1 += m0;

return x1;
}

int main() {
    long long N;
    std::cin >> N;

long long x1 = mod_inverse(4, 7);
    long long x2 = mod_inverse(7, 4);

long long restored_N = (4 * x1 * (N % 7) + 7 * x2 * (N % 4)) % (4 * 7);

if (restored_N == N && N - restored_N <= 2) {
        std::cout << "Yes" << std::endl;
    } else {
        std::cout << "No" << std::endl;
    }

return 0;
}

Этот код сначала находит обратные элементы x1 и x2, затем использует их для восстановления N и проверки условия.