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

Question

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

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

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 которые являются Dividable обоими 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, и он может быть эффективно вычислена Euclidean Algorithm, что неизбежно предполагает использование оператора модуля только в несколько раз (max {log(A), log(B)} раз, если быть точным), поэтому не должно быть никаких проблем с производительностью для вас.