4196. Шоколадные плитки

Тяжело переоценить роль шоколадных плиток для проведения традиционных олимпиад по программированию. Во-первых, питательное содержание шоколада значительно повышает количество гениальных идей у участников олимпиады, а геометрическая форма плитки – это, обычно, прямоугольник размером a × b квадратных частей 1 × 1, что в свою очередь напоминает модели многих задач.

Известны размеры шоколадной плитки a × b и количество участников олимпиады n. Членам жюри нужно определить, какого количества плиток шоколада достаточно, чтобы разломив их на единичные части, можно было бы разделить их поровну среди всех n участников олимпиады. То есть чтобы каждый получил бы одинаковое число квадратных долек 1 × 1.

Вход. Натуральные числа a, b, n. Все значения не превышают 100.

Выход. Вывести достаточное количество плиток шоколада.

Пример входа	Пример выхода
3 5 6	2

РЕШЕНИЕ

циклы

Анализ алгоритма

Каждая плитка шоколада содержит a * b единичных частей. Если cnt – достаточное количество плиток шоколада, то a * b * cnt должно нацело делиться на n. Значение cnt всегда существует, ищем его простым перебором: 1, 2, 3, … .

Реализация алгоритма

Читаем входные данные.

scanf("%d %d %d",&a,&b,&n);

s = a * b;

Искомое количество плиток шоколада cnt ищем простым перебором, начиная с 1.

cnt = 1;

while (a * b * cnt % n > 0)

cnt++;

Выводим ответ.

printf("%d\n",cnt);

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int a = con.nextInt();

int b = con.nextInt();

int n = con.nextInt();

int cnt = 1;

while (a * b * cnt % n > 0)

cnt++;

System.out.println(cnt);

con.close();

}

}

Python реализация

a, b, n = map(int,input().split())

cnt = 1

while a * b * cnt % n > 0:

cnt += 1

print(cnt)