Решение задачи "Орак и делители" с Codeforces

С пояснением   Просмотров: 25


Орак изучает теорию чисел, и его очень заинтересовали свойства делимости.

Для двух натуральных чисел a и b, a является делителем b если и только если существует такое натуральное число c, что a⋅c=b.

Для n≥2, обозначим за f(n) минимальный делитель n, отличный от 1.

Например, f(7)=7,f(10)=2,f(35)=5.

Для выбранного числа n Орак решил прибавить f(n) к n.

Например, если у него было число n=5, новое значение n будет равно 10. А если у него было число n=6, n станет равным 8.

Ораку так это понравилось, что он решил проделать подобные операции по несколько раз.

Для двух положительных чисел n и k, Орак попросил вас прибавить f(n) к n ровно k раз (обратите внимание, что n изменяется после каждой операции, соотвественно f(n) тоже может измениться) и сказать ему итоговое значение n.

Например, если Орак скажет вам, что n=5 и k=2, сначала вы должны прибавить f(5)=5 к n=5, и новое значение n станет равным n=10, после этого вы должны прибавить f(10)=2 к 10, и новое (и итоговое!) значение n будет равно 12.

Орак может задавать вам эти вопросы несколько раз.

Код

#include <bits/stdc++.h>

using namespace std;
void solve()
{
    long long n, k;
    cin >> n >> k;
    for(int i = 2; i <= n; ++i)
        if(n % i == 0){
            n += i;
            break;
        }
    n += (k - 1) * 2;
    cout << n << endl;
}
int main()
{
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

         

 Администратор Photo Автор: Администратор


Первое действие: находим наименьший делитель n и прибавляем к n.
Второе действие: нужно k - 1 раз выполнить операцию n += 2, т.к после первого действия n становится чётным.

Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться