@Rastr_0

Как составить формулу?

Задача: Дано целое число N и натуральное число P. Надо найти такое M, которое:
1) M >= N
2) M % P == 0
3) M - минимальное, которое удовлетворяет первые два пункта
Код есть, но с большими числами тесты по времени не проходит, помогите пожалуйста вывести формулу этого дела.
int main()
{
	long N, P;
	int M = 0;
	std::cin >> N >> P;
	int i = N;
	while (i % P != 0) 
	{
		i++;
	}
	std::cout << i;
}
  • Вопрос задан
  • 56 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
M%p = 0, значит M=k*p для какого-то целого k.

k*p >= N, значит k >= N/p.

k - целое, а справа в неравенстве может быть вещественное число. Раз k должно быть больше, то можно вещественное число округлить вверх.

k >= ceil(N/p).

слева и справа целые числа, надо найти минимальное k, значит k = ceil(N/p).

Отсюда весь ответ M = p*ceil(N/p)

ceil(N/p) можно подсчитать в целых числах в C, как (N+p-1)/p

Еще, если подумать, что вам нужно блищайшее делящееся на p число, то нужно дополнить N%p до p, то можно сделать так: N+(N%p ? p-N%p : 0)
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
iChar Санкт-Петербург
от 120 000 до 180 000 ₽
Яндекс Москва
от 100 000 до 300 000 ₽
28 янв. 2021, в 09:38
5000 руб./за проект
28 янв. 2021, в 09:32
3000 руб./за проект