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

Question

[rastr]

Задача: Дано целое число 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;
}

Answer 1

[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)

Comments

[Adamos]

Внимательно приглядевшись к условиям задачи, можно заметить, что нужно сначала проверить
if(N <= 0) {
M = 0;
} else {
... а вот тут уже формулы %)
}

[Wataru]

Adamos, Вообще говоря, если N отрицательно, то и M может быть отрицательно.

Тогда нужна такая формула: N+(N%p ? p-(-N)%p : 0)