Как найти общие вершины двух правильных многоугольников?
Скажите, пожалуйста, как можно решить эту задачу. Что-то совсем не могу понять как это можно реализовать..
В окружность вписаны N-угольник и M-угольник. Известно, что многоугольники правильные и имеют как минимум одну общую вершину. Вам необходимо подсчитать, сколько всего общих вершин имеют эти два многоугольника.
Ввод:
4 6
Вывод:
2
Ответы (2 шт):
Можно так.
Исходя из того, что многоугольник правильный, он разделит окружность, в которую вписан, на равные дуги. Остается найти "градусы", в которых угол многоульника накладывается на окружность, а потом посчитать совпадения для 2х многоульников.
N = 4
M = 6
N_set = set(i*360/N for i in range(N))
M_set = set(i*360/M for i in range(M))
print(len(N_set.intersection(M_set)))
Или можно просто найти НОД.
Ответом является НОД(n, m).
Возьмём отрезок [0, nm). Отложим на нём от нуля две арифметические прогрессии. Одна с шагом m, вторая - n. Сколько у них общих точек?
Пусть x - общая точка. Тогда x делится и на n и на m. Следовательно x делится на НОК(n, m).
И наоборот, любая точка вида k НОК(n, m) является общей.
Точек вида k НОК(n, m) на отрезке [0, nm) ровно nm / НОК(n, m). Это отношение равно НОД(n, m).
Задача была про математику, не про программирование:
import math
n = 4
m = 6
print(math.gcd(n, m))