Как посчитать количество делимых членов без использования оператора модуля?

Question

Учитывая три числа N, A и B. Найдите, как целые числа в диапазоне от 1 до N делятся на A или B. Я не могу использовать оператор модуля от диапазона 1 до N, потому что N может достигать 10^12, а затем I не хватит выделенного времени для программы, чтобы произвести вывод. Я попытался сформулировать уравнение, но не смог найти решение.

Входные ограничения:=

1<=N<=10^12
1<=A<=10^5
1<=B<=10^5

Answer 1

Я просто хочу использовать некоторое уравнение для оценки этой вещи, а не оператор модуля, потому что программа должна получить результаты в течение 1 секунды. Я пробовал это counter=(((int)(N/A))+((int)(N/B)))-((int)(N/(A*B))); но это не удается для входа N=200 A=20 B=8

Вы уже на правильном пути, ваша формула указывает, что вы пытаетесь применить принцип включения-исключения.

(int) (N/A) а также (int) (N/B) соответствует количеству целых чисел ≤ N которые делятся на A а также B соответственно.

Тем не мение, (int) (N/(A*B)) не дает правильное количество целых чисел ≤ N которые делятся на оба A а также B,

На самом деле, вы должны заменить (int) (N/(A*B)) от (int) (N/lcm(A,B)) для того, чтобы получить правильный результат. Вот lcm(A, B) возвращает наименьшее общее кратное A а также B,

Для реализации lcm(A, B) Функция, вы можете просто использовать следующую формулу:

lcm(A, B) = A * B / gcd(A, B);

где gcd(A, B) возвращает наибольший общий делитель A а также B и он может быть эффективно вычислен с помощью евклидова алгоритма, который неизбежно предполагает использование оператора модуля только очень мало раз (max {log(A), log(B)} время, чтобы быть точным), поэтому не должно быть никаких проблем с производительностью для вас.