Задача 5920. Источник: Поляков. Задание КИМ 15
(Е. Джобс) Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Найдите максимальное натуральное значение параметра А, при котором выражение
(ДЕЛ(z, 115) ∨ ДЕЛ(y, 78) ∨ ДЕЛ(х, 51)) → ДЕЛ(x·y·z, A)
тождественно истинно (то есть принимает значение 1 при любых натуральных значениях переменных х, y, z).
Решение
Если проанализировать выражение, то становится ясно, что все числа, которые делятся хотя бы на одно из числ в левой части выражения, должны делится на A. Решением данной задачи является наибольший общий делитель (НОД) чисел 115, 78 и 51.
Python
from math import gcd
print(gcd(115, gcd(78, 51)))
PascalABC
Стандартной реализации функции НОД в PascalABC нет. Эту функцию придется написать самостоятельно. Пример с вычислением в цикле. Можно использовать и рекурсивный вариант.
function gcd(a, b: Integer): Integer;
begin
while (a <> 0) and (b <> 0) do
if a > b then
a := a mod b
else
b := b mod a;
gcd := a + b;
end;
begin
Writeln(gcd(115, gcd(78, 51)));
end.
C++
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
cout << __gcd(115, __gcd(78, 51));
}
Visual C++
Не исключено, что в используемом компиляторе C++ реализации функции НОД не будет. Например, в Visual С++ ее нет. Тогда ее нужно реализовать самостоятельно. Пример рекурсивной функции с использованием тернарного оператора. Можно использовать и вычисление в цикле.
#include <iostream>
using namespace std;
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int main()
{
cout << gcd(115, gcd(78, 51));
}
Ответ
1