Проект Эйлера №5 | не могу понять решение

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 Aneesh Dandime    schedule 12.06.2015    source источник
comment
Ваш отладчик может. Вы это спросили?   -  person Bathsheba    schedule 12.06.2015
comment
Это кажется довольно простым и простым. Что вы не понимаете?   -  person nvoigt    schedule 12.06.2015
comment
ans % i - это НОД 'ans' и 'i'? @nvoigt   -  person Aneesh Dandime    schedule 12.06.2015
comment
@AneeshDandime Нет, это не так. Оператор % хорошо документирован. Ссылку на какой язык, если таковой имеется, вы используете, и у вас возникли проблемы с его поиском?   -  person    schedule 12.06.2015
comment
@hvd что делает ans *= i / (ans % i)? по логике это должно давать lcm из «ответов» и «я», верно?   -  person Aneesh Dandime    schedule 12.06.2015
comment
@AneeshDandime Нет. Опять же, ans % i не является НОД. Посмотрите, что он делает, в справочнике по языку. Поскольку ans % i не является НОД, ans *= i / (ans % i); не может вычислить НОК.   -  person    schedule 12.06.2015
comment
@hvd я знаю, что% дает остаток. :(   -  person Aneesh Dandime    schedule 12.06.2015
comment
@AneeshDandime Тогда извините, я не понимаю, как вы думаете, ans *= i / (ans % i) вычисляет LCM. ans *= i / gcd(ans, i) будет вычислять LCM, а (как вы теперь знаете) ans % i не является gcd(ans, i), поэтому ans *= i / (ans % i) обязательно вычисляет что-то еще. Я не думаю, что есть общее название для этой операции. Это просто три операции, объединенные в одну, и, вероятно, вы уже знаете * и /.   -  person    schedule 12.06.2015
comment
@hvd Его проблема (и, честно говоря, моя тоже) математическая, не связанная с C ++. Он знает, что делают *, / и %. Дело в том, ПОЧЕМУ это работает, чтобы вычислить это? Если 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
comment
@hvd Итак, i / (ans % i) в основном дает число, которое нужно умножить на ans, так что ans теперь делится на < б>я .   -  person Aneesh Dandime    schedule 12.06.2015
comment
@FabioTurati В основном согласен. Проблема ОП является как математической, так и связанной с С++. В более ранних комментариях ОП предложил, чтобы оператор % возвращал GCD. Эта часть не является математической задачей. Остальное (без каламбура).   -  person    schedule 12.06.2015
comment
@FabioTurati, о, наконец. Спасибо большое. Моя проблема именно то, что вы описали в своем комментарии! Извините за всю эту путаницу. Я не правильно объяснил свое сомнение.   -  person Aneesh Dandime    schedule 12.06.2015
comment
@hvd, а теперь не могли бы вы объяснить, как линия работает математически?   -  person Aneesh Dandime    schedule 12.06.2015
comment
Я подозреваю, что каким-то образом ans % i действительно равно gcd(ans, i) из-за особого способа построения ans (ans кратно каждому числу до i, но не включая его). Другими словами, алгоритм Евклида, примененный к ans и i, всегда будет выполняться за одну итерацию. Однако в настоящий момент формальное доказательство этого утверждения ускользает от меня.   -  person Igor Tandetnik    schedule 13.06.2015
comment
@IgorTandetnik То же самое, я не могу это доказать.   -  person Aneesh Dandime    schedule 13.06.2015
comment
@Igor: то же самое здесь, я думаю, что это работает как gcd, но я не могу понять, почему. Аниш: возможно, вы могли бы задать этот вопрос на math.stackexchange.com, я думаю, что есть очень хороший шанс, что кто-то там сможет ответить. Если да, киньте сюда ссылку, интересно будет почитать.   -  person Fabio says Reinstate Monica    schedule 13.06.2015
comment
@FabioTurati хорошо, я задам этот вопрос на [ссылка] (math.stackexchange.com). Если у кого-то появится ответ, я опубликую ссылку здесь.   -  person Aneesh Dandime    schedule 13.06.2015
comment
@FabioTurati смотрите принятый ответ ниже. Это доказывает, что алгоритм не работает.   -  person Aneesh Dandime    schedule 16.06.2015
comment
@AneeshDandime Спасибо, что нашли время, чтобы сообщить мне, я очень ценю это. Так что в основном алгоритм на самом деле не работает, он просто случайно работает для небольших значений. Вот вам и довольно простая и понятная логика, и отладчик, который понимает ее, как говорили другие. Мне просто жаль, что один только мой голос не может компенсировать ваши отрицательные голоса. Кто-то даже проголосовал за другой вопрос glear14195. Иногда я действительно ненавижу этот сайт...   -  person Fabio says Reinstate Monica    schedule 16.06.2015
comment
@FabioTurati все в порядке. Плевать на минусы. :)   -  person Aneesh Dandime    schedule 16.06.2015


Ответы (1)


Приведенный выше код не дает правильного вывода для ряда тестовых случаев. Например:

    Output     N   Correct Answer
    232792560  19  232792560
    1059261584 23  5354228880
    1117182544 25  26771144400
    1886839328 27  80313433200

Вы можете проверить ответ Фама Трунга на похожий вопрос, который я задал.

person glear14195    schedule 16.06.2015