Как я могу найти такое количество пар a, b & lt; N, чтобы GCD (a, b) = x?
Я пытаюсь решить SPOJ проблема PGCD, который спрашивает, сколько простых чисел появляется в таблице наибольших общих делителей.
Первая идея, которая пришла мне в голову, — это сначала создать простые числа путем просеивания.
Тогда для каждого простого п, посмотрим сколько пар (, б), где а также б меньше заданных границ, удовлетворяют GCD(a,b)=p,
Например, сколько пар меньше (20, 20) удовлетворяют GCD (a, b) = 7?
Конечно, как уже упоминалось, а также б ограничены.
Так возможно ли обратить вспять GCD? Или это решение полностью неверно?
Решение
Очевидно, что функция GCD не является обратимой / обратимой, потому что, например,
- GCD (10,15) == 5
- GCD (5, 15) == 5
Так что если вам дают 5 и пытаются угадать входные данные, это невозможно.
Возможно, я что-то здесь упускаю, потому что я не понимаю, что вы говорите об ограничении, но я думаю, что вы несете ответственность за лучшее объяснение проблемы. Какая информация у вас есть и какую информацию вы пытаетесь вычислить? Пример входов и выходов был бы действительно полезен. Также корректура и проверка орфографии.
Другие решения
Других решений пока нет …