2520 — это наименьшее число, которое можно разделить на каждое из чисел от 1 до 10 без остатка. Какое наименьшее положительное число делится без остатка на все числа от 1 до N?
Формат ввода: первая строка содержит T, обозначающее количество тестовых случаев. Затем следуют T строк, каждая из которых содержит целое число N.
Формат вывода: распечатайте требуемый ответ для каждого теста.
Ограничения: 1≤T≤10 1≤N≤40
полная ссылка на вопрос
Вот код, результаты которого были приняты hackerrank, но у меня возникли проблемы с пониманием решения.
Кто-нибудь может объяснить это?
Что делает строка ans *= i / (ans % i)? Остальное я понял.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
bool check_if_prime(long n);
int main(void) {
long t, n, i, ans = 1;
std::cin >> t;
while(t--){
std::cin >> n;
for(i = 2; i <= n; ++i){
if(!check_if_prime(i)){
if(ans % i)
ans *= i / (ans % i);
}else
ans *= i;
}
std::cout << ans << std::endl;
ans = 1;
}
return 0;
}
bool check_if_prime(long n){
if(n == 2)
return true;
for(long i = 2; i * i <= n; ++i){
if(n % i == 0)
return false;
}
return true;
}
%
хорошо документирован. Ссылку на какой язык, если таковой имеется, вы используете, и у вас возникли проблемы с его поиском? - person   schedule 12.06.2015ans % i
не является НОД. Посмотрите, что он делает, в справочнике по языку. Посколькуans % i
не является НОД,ans *= i / (ans % i);
не может вычислить НОК. - person   schedule 12.06.2015ans *= i / (ans % i)
вычисляет LCM.ans *= i / gcd(ans, i)
будет вычислять LCM, а (как вы теперь знаете)ans % i
не являетсяgcd(ans, i)
, поэтомуans *= i / (ans % i)
обязательно вычисляет что-то еще. Я не думаю, что есть общее название для этой операции. Это просто три операции, объединенные в одну, и, вероятно, вы уже знаете*
и/
. - person   schedule 12.06.2015*
,/
и%
. Дело в том, ПОЧЕМУ это работает, чтобы вычислить это? Еслиans
нельзя разделить наi
, самый простой способ сделать его делимым наi
— это умножить его наi
. Но это может быть слишком много: если у вас естьans=6
иi=4
, вы не хотитеans *= 4
, это будет слишком много, вы на самом деле хотитеans *= 2
. Здесь это достигается умножением наi
и делением наans % i
. Вопрос в том, почему математически работает деление наans % i
? - person Fabio says Reinstate Monica   schedule 12.06.2015%
возвращал GCD. Эта часть не является математической задачей. Остальное (без каламбура). - person   schedule 12.06.2015ans % i
действительно равноgcd(ans, i)
из-за особого способа построенияans
(ans
кратно каждому числу доi
, но не включая его). Другими словами, алгоритм Евклида, примененный кans
иi
, всегда будет выполняться за одну итерацию. Однако в настоящий момент формальное доказательство этого утверждения ускользает от меня. - person Igor Tandetnik   schedule 13.06.2015