На платформе была обновлена модель тестирования решений.

Для решения данной задачи достаточно было проверять введённый пинг на принадлежность к 4 числовым отрезкам, а именно:

• Если $$$n \in [0, 21)$$$, то выводить amazing!.
• Иначе если $$$n \in [21,\ 51)$$$, то выводить good!.
• Иначе если $$$n \in [51,\ 151)$$$, то выводить bad!.
• В противном случае $$$n \in [51,\ 1001)$$$, тогда нужно вывести very bad!.

Итоговая асимптотика решения: $$$\mathcal{O}(1)$$$

n = int(input())
if n < 21:
    print("amazing!")
elif n < 51 and n > 20:
    print("good!")
elif n < 151 and n > 50:
    print("bad!")
else:
    print("very bad!")

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

Способов решения данной задачи существует очень много, поэтому разберем самое оптимальное.

В условии указано, что нужно найти любой интересный подотрезок, длина которого $$$\le n - 1$$$. Тогда не сложно догадаться, что достаточно вывести отрезок из $$$1$$$ элемента — максимума массива $$$a$$$, что будет удовлетворять условию задачи.

Итоговая асимптотика решения: $$$\mathcal{O}(n)$$$

n = int(input())
print(max(list(map(int, input().split()))))

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

Вычисление по данной формуле напрямую, скорее всего, не получится, так как $$$n$$$ может достигать $$$10^9$$$ и числа будут огромными. Но можно заметить, что $$$4 = 2 \times 2$$$, $$$21 = 3 \times 7$$$, $$$14 = 2 \times 7$$$, $$$15 = 3 \times 5$$$, $$$6 = 2 \times 3$$$. Используя стандартные правила работы со степенями, можно представить числитель и знаменатель в виде произведения простых чисел 2, 3, 5, 7 в некоторых степенях. При делении $$$a$$$ на $$$b$$$ число $$$n$$$ везде сократится и останется только число 200. То есть, $$$\cfrac{a}{b} = 200$$$. Значит $$$\cfrac{a \times n}{b} = 200 \times n$$$, значит, для решения задачи необходимо просто считать число $$$n$$$ и вывести $$$200 \times n$$$. Также стоит заметить, что при больших значениях $$$n$$$ в некоторых языках программирования ответ может не помещаться в 32-битный целочисленный тип данных, поэтому необходимо использовать 64-битный тип данных.

Итоговая асимптотика решения: $$$\mathcal{O}(1)$$$

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int n;
    cin >> n;
    cout << 200ll * n << "\n";
    return 0;
}

n = int(input())
print(n * 200)

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

Для решения данной версии задачи достаточно было перебрать все возможные числа, которые мог загадать Илья. Таким образом, для каждого обратного $$$i$$$-го числа нужно проверять его на соответствие сумм чисел на четных и нечетных позициях, а также количества нулей, для предложенного $$$j$$$-го тестового набора входных данных. Так как перебираемые числа довольно малы, то асимптотикой их проверки можно пренебречь. В случае успешного нахождения загаданного числа нужно вывести для $$$j$$$-го набора входных данных ответ YES, в противном случае, если такое число при заданных Ильей значениях $$$a$$$, $$$b$$$ и $$$k$$$ не существует или является больше, чем $$$10^4$$$, ответ NO.

Итоговая асимптотика решения: $$$\mathcal{O}(t \cdot n)$$$, где $$$n$$$ ($$$1 \le n \le 10^4$$$) — число, загаданное Ильей.

for _ in range(int(input())):
    a, b, k = map(int, input().split())
    answer = False
    for i in range(1, 10 ** 4 + 1):
        s = str(i)[::-1]
        a_s = 0
        b_s = 0
        k_s = 0
        for j in range(len(s)):
            if j % 2 == 0:
                b_s += int(s[j])
                if s[j] == '0':
                    k_s += 1
            else:
                a_s += int(s[j])
                if s[j] == '0':
                    k_s += 1
        if a == a_s and b == b_s and k == k_s:
            print("YES")
            answer = True
            break
    if not answer:
        print("NO")

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

В начале давайте найдём все простые числа от в диапазоне [1, 100]. Это можно сделать вручную, с помощью алгоритмов, например, решета Эратосфена, перебором или любым другим способом. Мы получим 25 простых чисел от 1 до 100.

Можно понять, что нет смысла делать запрос с числом $$$x$$$, если в его разложении на простые числа есть числа больше 100 или степень какого-либо из простых чисел превосходит 1.

Заметим, что так как $$$n$$$ — простое число, то если мы хотим проверить, является ли число $$$n$$$ каким-то простым числом $$$x$$$ или $$$y$$$, мы можем проверить, делится ли число $$$x \times y$$$ на $$$n$$$. Если оно делится, то $$$n$$$ является либо числом $$$x$$$, либо числом $$$y$$$. Таким образом, за один запрос мы можем узнавать информацию, является ли $$$n$$$ числом $$$x$$$ сразу для нескольких чисел $$$x$$$.

Перейдём к самому решению. Давайте расположим все 25 простых чисел от 1 до 100 в порядке возрастания. А дальше можно применить бинпоиск. Изначально считаем, что число $$$n$$$ находится в отрезке от первого простого числа до последнего (из нашего списка). Возьмём число $$$x$$$ равное произведению первой половины нашего отрезка простых чисел. Проверим с помощью запроса, входит ли число $$$n$$$ в эту половину отрезка. Если входит, сдвинем правую границу в середину отрезка, иначе левую. И будем уменьшать отрезок постоянно в 2 раза, пока у нас не останется лишь одно число. Это число и будет ответом.

Может показаться, что $$$x$$$ в некотором запросе может стать больше $$$10^{18}$$$, но это не так: произведение первой половины чисел равно $$$7420738134810$$$, что меньше $$$10^{18}$$$. Если мы сдвинем границы влево, то произведение больше не станет. Если сдвинем вправо, то получим произведение $$$15805487167$$$, что тоже подходит под ограничения. Соответственно, отрезки, лежащие внутри тоже подходят, а справа произведение равно $$$19657257924641$$$, и оно тоже меньше $$$10^{18}$$$, а значит произведение всех последующих отрезков чисел тоже меньше $$$10^{18}$$$.

Значит, решение работает и сделает около $$$\log_2 25 $$$ запросов, то есть не больше $$$5$$$ запросов.

Итоговая асимптотика решения: $$$\mathcal{O}(1)$$$.

#include <bits/stdc++.h>
// #include "testlib.h"

using namespace std;
#define ll long long
#define vec vector

const ll INF = 1e9 + 7;
const ll NOT_INF = 1e9 + 7;
const string YES = "YES";
const string NO = "NO";

void rec(vec<int> v){
    ll L = 1;
    for(int i = 0; i < v.size() / 2 + v.size() % 2; i++){
        L *= v[i];
    }
    cout << "? " << L << '\n';
    cout.flush();
    int n; cin >> n;
    if (n){
        if (L == v[0]){ cout << "!" << " " << L; return;}
        else {
            vec<int> v4;
            for(int i = 0; i < v.size() / 2 + v.size() % 2; i++){
                v4.push_back(v[i]);
            }
            rec(v4);
            return;
        }
    }else {
        if (L == v[0]) {  cout << "!" << " " << v[1];}
        else {
            vec<int> v4;
            for(int i = v.size() / 2 + v.size() % 2; i < v.size(); i++){
                v4.push_back(v[i]);
            }
            rec(v4);
            return;
        }
    }
}

void test_case(){
    vector<int> v1 {
            2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43
    }, v2 {
            47, 53, 59, 61, 67, 71, 73, 79
    }, v3 {
            83, 89, 97
    };
    ll L = 1;
    for(auto i: v1){
        L *= i;
    }
    cout << "? " << L << '\n';
    cout.flush();
    int n; cin >> n;
    if (n){
        rec(v1);
    }else {
        L = 1;
        for (auto i: v2) {
            L *= i;
        }
        cout << "? " << L << '\n';
        cout.flush();
        cin >> n;
        if (n) {
            rec(v2);
        } else {
            rec(v3);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while(t-->0){
        test_case();
    }
}

from functools import reduce
l, r, p = 0, 25, [*map(int, '2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97'.split())]
while r - l > 1:
    m = (l + r) // 2
    print('?', reduce(lambda x, y: x * y, p[l:m]))
    if input() == '1':
        r = m
    else: 
        l = m
print('!', p[l])

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

Во входных данных мы имеем остановки и для каждой из них расписание некоторого $$$P$$$-го автобуса. Тогда давайте заведем словарь $$$a$$$, в котором мы будем хранить расписание для каждой $$$i$$$-й остановки, гдк ключём будет являться название остановки, а значением — массив $$$a[i]$$$, который будет состоять из чисел, обозначающих значения расписания в минутах (для удобства использования данных в дальнейшем).

После преобразования в удобный вид использования входных данных нам нужно ответить на $$$t$$$ запросов, для которых ответом является нахождение ближайшего следующего рейса $$$P$$$-го автобуса для $$$t_i$$$ остановки в заданное время.

Очевидно, что из-за возможного большого количества данных для каждой из остановок, перебирать и сравнивать заданное время с значениями расписания для текущей $$$t_i$$$ остановки отнюдь не оптимально, тогда на помощь к нам приходит двоичный поиск!

Для того, чтобы реализовать быстрое нахождение ближайшего рейса $$$P$$$-го автобуса, нам потребуется для каждой заданной $$$i$$$-й остановки изначально отсортировать значения их расписаний. После чего, отвечая на $$$t_i$$$ запрос, мы можем реализовать поиск ближайшего следующего рейса в массиве $$$a_{t_i}$$$ при помощи двоичного поиска, а именно применив алгоритм бинпоиске по массиву upper_bound, который будет возвращать ссылку на значение в минутах нужного нам рейса $$$P$$$-го маршрута. В случае, если значение полученного результата принадлежит $$$a_{t_i}$$$, тогда останется вывести модуль разности между заданным и полученным временем. В противном случае вывести :(.

Итоговая асимптотика решения: $$$\mathcal{O}(n \cdot q \cdot log \cdot q + t \cdot log \cdot q)$$$

#include <bits/stdc++.h>
//#include "testlib.h"

using namespace std;
#define ll long long
#define vec vector

const ll INF = 1e9 + 7;
const ll NOT_INF = 1e9 + 7;
const string YES = "YES";
const string NO = "NO";

void test_case(){
    ll n;
    cin >> n;
    map<string, vec<ll>> a;
    ll p = (ll)pow(10, 5);
    for(int i = 0; i < n; i++){
        string name; ll q;
        cin >> name >> q;
        while(q--){
            ll h, m;
            cin >> h >> m;
            a[name].push_back(h * p + m);
        }
    }
    for(auto &i: a){
        sort(i.second.begin(), i.second.end());
    }
//    for(auto &i: a){
//        cout << i.first << " ! ost\n";
//        for(auto j: i.second){
//            cout << "Schedule: " << j.h << " h. " << j.m << " m.\n";
//        }
//    }

    int t; cin >> t;
    while(t-->0){
        string name; ll h, w;
        cin >> name >> h >> w;
        auto mx = upper_bound(a[name].begin(), a[name].end(), h * p + w);
        if (mx != a[name].end()){
            // cout << *mx  << ' ' <<h * p + w<< '\n';
            cout << abs(*mx - (h * p + w)) << '\n';
        }else
            cout << ":(" << '\n';
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int test_c = 1;
    //cin >> test_c ;
    while(test_c-->0){
        test_case();
    }
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

Первое, что требовалось понять — это удобный принцип рассмотрения станций. Не сложно было догадаться, что одним из возможных вариантов оптимальных решений являлось движение от станции с наименьшим значением загруженности к наибольшей. Таким образом, достаточно было отсортировать массив $$$a$$$ для проведения последующих действий... (Также отметим, что в начальный момент времени {по условию} сумма степеней возмущенности равна $$$0$$$)

Далее, для полного решения задачи, необходимо иметь решения ее подзадач. Заведем для этих целей массив $$$dp$$$, в котором мы будем хранить наименьшее значение возмущенности Ильи после посещения $$$i$$$-й станции метрополитена. Также введём обозначение:

Разберём ситуацию для $$$n\ =\ 1$$$, тогда совсем не сложно осознать, что Илья посетит только одну станцию и соответственно степень возмущённости будет равна единице. Тогда наименьшая сумма степеней будет равняться единице. ($$$dp[1] = 1$$$)

Разберём ситуацию для $$$n\ =\ 2$$$, тогда мы рассмотрим два случая изменения степени возмущённости Ильи, а именно:

• Если модуль разности значений загруженности станций $$$a_1$$$ и $$$a_2$$$ не больше, чем значение параметра $$$k$$$ ($$$|a_1 - a_2| \le k $$$), то после посещения данных пунктов метрополитена суммарная степень возмущённости для этих станций будет равна единице. Тогда наименьшая сумма степеней возмущённости будет равна единице. ($$$dp[2] = 1$$$)

• В противном случае для каждой из станций степень возмущённости будет равна единице. Тогда после посещения двух станций степень возмущённости будет равняться двум. ($$$dp[2] = 2$$$)

Разберём ситуацию для $$$n\ =\ 3$$$, тогда мы рассмотрим три случая изменения степени возмущения Ильи, а именно:

• Если разность максимального и минимального значения отрезка $$$b\ =\ [a_1, a_2, a_3]$$$ не превышает значения параметра $$$d$$$ ($$$b_{max} - b_{min} \le d$$$), то после посещения трёх пунктов метрополитена суммарная степень возмущённости этих станций будет равна $$$1$$$. Тогда наименьшая сумма степеней будет равняться единице. ($$$dp[3] = 1$$$)

• Иначе, если модуль разности значений загруженности станций $$$a_2$$$ и $$$a_3$$$ не больше, чем значение параметра $$$k$$$ ($$$|a_2 - a_3| \le k $$$), то после посещения данных пунктов метрополитена суммарная степень возмущённости этих станций будет равно единице. Тогда наименьшая сумма степеней будет равняться двум ($$$dp[3] = 2 $$$), так как получится следующее разбиение на комбинации:

• В противном случае значение степени возмущённости увеличится на единицу и будет равняться $$$dp[3] = dp[2] + 1$$$. (Так как мы рассматриваем еще и значение $$$dp[2]$$$, которое получилось при рассмотрении первых двух элементов отсортированного массива $$$a$$$, исходя из предыдущего пункта). Тогда мы получаем следующую комбинацию:

Для решения каждой последующей подзадачи, для которых $$$n > 3$$$, мы спокойно можем воспользоваться значениями $$$dp[1],\ dp[2],\ dp[3]$$$ по умолчанию. Таким образом, для определения наименьшей суммы степеней возмущённости каждой последующей $$$i$$$-й подзадачи, нам нужно рассматривать следующие эффективные комбинации получения наименьшей суммы степеней:

• Если разность максимального и минимального значения отрезка $$$b\ =\ [a_{i - 2}, a_{i - 1}, a_i]$$$ (посещение трех последних станций) не превышает значения параметра $$$d$$$ ($$$b_{max} - b_{min} \le d$$$), тогда рассмотрим две последние посещённые станции:

• • Если модуль разности значений загруженности станций $$$a_{i - 1}$$$ и $$$a_{i}$$$ не больше, чем значение параметра $$$k$$$ ($$$|a_{i - 1} - a_i| \le k $$$), то значение степени возмущённости для этих пунктов метрополитена будет равна единице, а наименьшая сумма степеней для помещенных станций будет равна $$$dp[i] = min(dp[i - 2] + 1, dp[i - 3] + 1)$$$.

• • В противном случае для этих пунктов метрополитена степень возмущённости будет равняться единице, а наименьшая сумма степеней для посещённых станций будет равна $$$dp[i] = dp[i - 3] + 1$$$ (Изменять значение степени возмущённости для каждой станции по отдельности для данного случая не имеет смысла). Получается следующее комбинирование станций при измерении степеней:

• Иначе, если модуль разности значений загруженности станций $$$a_{i - 1}$$$ и $$$a_{i - 2}$$$ не больше, чем значение параметра $$$k$$$ ($$$|a_{i - 1} - a_{i - 2}| \le k $$$), то для этих пунктов метрополитена суммарная степень возмущённости будет равна единице, а наименьшее значение суммы степеней для текущей подзадачи равно $$$dp[i] = dp[i - 2] + 1$$$. Таким образом получаем следующее комбинирование:

• В противном случае мы рассматриваем $$$i$$$-ю станцию отдельно и значение степени возмущённости для неё будет равно единственное, следовательно наименьшее значение суммы степеней для текущей подзадачи равно $$$dp[i] = dp[i - 1] + 1$$$. Таким образом получаем следующее комбинирование:

После рассмотрения конечной посещённой станции итоговым ответом будет являться значение $$$dp[n]$$$.

Итоговая асимптотика решения: $$$\mathcal{O}(t \cdot (n \cdot log \cdot n + n))$$$

#include <bits/stdc++.h>
//#include "testlib.h"
using namespace std;
#define ll long long
#define vec vector

const ll INF = 1e9 + 7;
const string YES = "YES";
const string NO = "NO";

void test_case(int argc, char *argv[]){
    ll n, k, d; cin >> n >> k >> d;
    vec<ll> a(n);
    vec<ll> dp(n);
    cin >> a[0];
    for(int i = 1; i < n; i++){
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    dp[0] = 1;
    if (n >= 2){
        if (abs(a[0] - a[1]) <= d){
            dp[1] = 1;
        }else {
            dp[1] = 2;
        }
    }
    if (n >= 3){
        if (abs(max(a[0], max(a[1], a[2])) - min(a[0], min(a[1], a[2]))) <= k){
            dp[2] = 1;
        }else if (abs(a[1] - a[2]) <= d){
            dp[2] = 2;
        }else {
            dp[2] = dp[1] + 1;
        }
    }
    if (n > 3){
        for(int i = 3; i < n; i++){
            if (max(a[i], max(a[i - 1], a[i - 2])) - min(a[i], min(a[i - 1], a[i - 2])) <= k){
                if (abs(a[i - 1] - a[i]) <= d) {
                    dp[i] = min(dp[i - 2] + 1, dp[i - 3] + 1);
                }else {
                    dp[i] = dp[i - 3] + 1;
                }
            }else if (abs(a[i - 1] - a[i]) <= d) {
                dp[i] = dp[i - 2] + 1;
            }else {
                dp[i] = dp[i - 1] + 1;
            }
        }
    }
    cout << dp[n - 1] << '\n';
}

int main(int argc, char *argv[]){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1; cin >> t;
    while(t-->0){
        test_case(argc, argv);
    }
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

Более формально, в задаче необходимо найти все натуральные числа $$$n = 2 \times k^2 + 1$$$, где $$$k$$$ — натуральное число, и $$$n$$$ является палиндромом. Можно предположить, что таких чисел существует не очень много, и попробовать запустить поиск таких чисел.

Перебор числа $$$n$$$ будет выполняться слишком долго, так как $$$n$$$ может достигать $$$10^{18}$$$. Нужно придумать способ оптимальнее. Заметим, что так как $$$n \le 10^{18}$$$, то $$$k \le \sqrt{\cfrac{10^{18} - 1}{2}}$$$, то есть $$$k$$$ не превосходит $$$10^9$$$. Значит, можно перебирать число $$$k$$$ вместо $$$n$$$, вычислять $$$n$$$ и проверять его, является ли оно палиндромом.

Асимптотика перебора: $$$\mathcal{O}(\sqrt{N} \log{N})$$$, где $$$N$$$ — максимально возможное $$$n$$$, в нашем случае $$$N = 10^{18}$$$. (Будем считать, что проверка, является ли число палиндромом, выполняется за его длину, то есть за $$$\mathcal{O}(\log{N})$$$)

Может показаться, что этот перебор будет выполняться довольно долго, но на практике достаточно от 40 секунд до 15 минут, в зависимости от языка программирования и реализации алгоритма.

В результате перебора можно понять, что подходящих под условие задачи чисел всего 21: $$$3$$$, $$$9$$$, $$$33$$$, $$$99$$$, $$$393$$$, $$$969$$$, $$$38211283$$$, $$$91044019$$$, $$$95855859$$$, $$$357727753$$$, $$$10284648201$$$, $$$91637373619$$$, $$$93323232339$$$, $$$100083380001$$$, $$$3119172719113$$$, $$$100540454045001$$$, $$$302791646197203$$$, $$$982885848588289$$$, $$$9188622002268819$$$, $$$150434127721434051$$$, $$$355553961169355553$$$.

Теперь мы знаем все подходящие числа и то, что их не так много. Значит, мы можем записать все эти числа в виде массива в коде программы и потом с ними работать, не пытаясь их посчитать при каждом запуске.

На запросы можно отвечать разными способами. Можно искать с помощью бинпоиска индекс минимального числа, которое не меньше $$$l$$$ и индекс минимального числа, которое больше $$$r$$$. И тогда ответ — это разность этих индексов. Тогда асимптотика решения будет $$$\mathcal{O}(t \log{B})$$$, где $$$B$$$ — это количество подходящих чисел, $$$B = 21$$$.

Но можно поступить и проще, так как у нас всего 21 число, для каждого запроса можно перебирать каждое число и проверять, лежит ли оно в необходимом диапазоне. Тогда асимптотика решения будет $$$\mathcal{O}(tB)$$$, где $$$B$$$ — это количество подходящих чисел, $$$B = 21$$$.

Вероятно, должны существовать способы оптимизировать перебор чисел, чтобы можно было перебирать их прямо в решении, перед ответом на запросы, или даже найти их все без перебора, но задача предполагает решение описанным способом.

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
ll max_n = 1'000'000'000'000'000'000ll;
 
bool is_palindrome(ll x) {
    ll y = 0;
    for (ll t = x; t > 0; t /= 10) {
        y = 10 * y + t % 10;
    }
    return x == y;
}
 
int main() {
    for (ll x = 1, d = 3; 2 * x + 1 <= max_n; x += d, d += 2) {
        ll n = 2 * x + 1;
        if (is_palindrome(n)) {
            cout << n << "\n";
        }
    }
}

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
vector<ll> nums = {
        3ll, 9ll, 33ll, 99ll, 393ll, 969ll, 38211283ll, 91044019ll, 95855859ll,
        357727753ll, 10284648201ll, 91637373619ll, 93323232339ll, 100083380001ll,
        3119172719113ll, 100540454045001ll, 302791646197203ll, 982885848588289ll,
        9188622002268819ll, 150434127721434051ll, 355553961169355553ll
};
 
void solve() {
    ll l, r, ans = 0;
    cin >> l >> r;
 
    for (ll x: nums) {
        if (l <= x && x <= r) {
            ans++;
        }
    }
 
    cout << ans << "\n";
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    ll t = 1;
    cin >> t;
    for (ll i = 0; i < t; ++i) {
        solve();
    }
}

• Не решал
• Хорошая задача
• Средняя задача
• Плохая задача

В данной задаче требовалось вывести любое целое четное и одновременно простое число, лежащее на промежутке от $$$0$$$ до $$$n$$$. После не долгих размышлений, не сложно понять, что такое число только одно, а именно: $$$2$$$.

Асимптотика решения: $$$\mathcal{O}(1)$$$

n = int(input())
print(2)

Ожидается...

Ожидается...

В этой задаче необходимо было использовать расширенный алгоритм Евклида для нахождения ответа.

Будем считать, что $$$c > 0$$$. Если $$$c = 0$$$, то можно вывести любое число (так как гарантируется, что ответ всегда существует). Иначе, если $$$c < 0$$$, то его можно сделать положительным, взяв математический остаток от деления на $$$m$$$.

Составим диофантово уравнение $$$cx + my = (b_i - d)$$$. Тогда можно заметить, что $$$a_i = x\ \%\ m$$$. Само число $$$x$$$, как уже было сказано, можно найти с помощью расширенного алгоритма Евклида за $$$\mathcal{O}(\log \max(c, m))$$$.

Можно заметить, что достаточно один раз найти решение уравнения $$$cx + my = \gcd(c, m)$$$. Пусть это решение равно $$$(x_0; y_0)$$$, тогда для $$$i$$$-го числа ответом является $$$x_0 \times \frac{b_i - d}{\gcd(c, m)}$$$ (Возможно, придётся взять остаток от деления на $$$m$$$)

Асимптотика решения: $$$\mathcal{O}(n + \log \max(c, m))$$$.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct g_res {
    ll d, x, y;
};

ll mm(ll a, ll m) {
    return (a % m + m) % m;
}

g_res gcd_ext(ll a, ll b) {
    if (b == 0) {
        return {a, 1, 0};
    }
    g_res g = gcd_ext(b, a % b);
    return {g.d, g.y, g.x - g.y * (a / b)};
}

void solve() {
    ll n, c, d, m, bi;
    cin >> n >> c >> d >> m;
    c = mm(c, m);
    d = mm(d, m);

    if (c == 0) {
        for (ll i = 0; i < n; ++i) {
            cout << "0";
            if (i != n - 1) {
                cout << " ";
            }
        }
        cout << "\n";
        return;
    }

    g_res g = gcd_ext(c, m);
    for (int i = 0; i < n; ++i) {
        cin >> bi;
        cout << mm(mm(bi - d, m) / g.d * g.x, m);

        if (i != n - 1) {
            cout << " ";
        }
    }

    cout << "\n";
}

int main() {
#ifndef NEKSTAS
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#endif

    int t = 1;
//    cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
}

Можно заметить, что пожелание каждого друга Алексея представляется в виде битовой маски длины $$$30$$$, где $$$i$$$-й справа бит равен $$$1$$$, если друг хочет подарок $$$i$$$-го вида и $$$0$$$ — если не хочет.

Тогда задача сводится к нахождению побитового ИЛИ всех чисел на отрезке массива от $$$l$$$ до $$$r$$$.

Её можно решать разными способами.

Например, можно посчитать для каждого бита по отдельности префиксные суммы (к текущей префиксной сумме прибавляется $$$1$$$, если $$$j$$$-й бит равен $$$1$$$) и тогда $$$j$$$-й бит в ответе на запрос равен $$$1$$$, если количество единичных битов на отрезке больше нуля ($$$p_{r,j} - p_{l-1,j} > 0$$$). Асимптотика: $$$\mathcal{O}((n + q) \log A)$$$.

Другое решение заключается в том, чтобы построить Дерево Отрезков на массиве $$$a$$$ на нахождение побитового ИЛИ чисел на отрезке. Асимптотика: $$$\mathcal{O}(n + q \log n)$$$

#include <bits/stdc++.h>

#define len(x) ((int) (x).size())

using namespace std;
typedef long long ll;

const ll INF = (1ll << 62);
const int INF_I = 0x3f3f3f3f;


void config_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed;
    cout.precision(20);
}


void solve();


int main() {
    config_io();
    auto start = chrono::high_resolution_clock::now();
    solve();
    auto end = chrono::high_resolution_clock::now();

#ifdef NEKSTAS_LOCAL
    cerr << "Execution time: "
         << chrono::duration_cast<chrono::milliseconds>(end - start).count()
         << " ms" << endl;
#endif

    return 0;
}


void solve() {
    int n, q, z = 30;
    cin >> n >> q;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    vector<vector<int>> p(n + 1, vector<int>(z, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < z; ++j) {
            p[i + 1][j] = p[i][j] + !!(a[i] & (1 << j));
        }
    }

    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        l--;

        int ans = 0;
        for (int j = 0; j < z; ++j) {
            ans += (p[r][j] - p[l][j] > 0) << j;
        }
        cout << ans << "\n";
    }
}

Ожидается...

Ожидается...

Это довольно стандартная задача на теорию чисел. Как было написано в условии, коэффициент перед $$$k$$$-м слагаемым в разложении $$$n$$$-й степени равен $$$C_k^n$$$, то есть, задача сводится к нахождению $$$C_k^n$$$ за $$$\mathcal{O}(1)$$$ или $$$\mathcal{O}(\log n)$$$ с предподсчётом за некоторую асимптотику.

Давайте посчитаем массив $$$f$$$ длины $$$n + 1$$$, где $$$f_i = i!$$$ по модулю $$$10^9 + 9$$$ ($$$i$$$ факториал). Это можно сделать следующей рекуррентной формулой: $$$f_0 = 1$$$, $$$f_i = f_{i-1} \times i\ \%\ M$$$, где $$$M = 10^9 + 9$$$.

Теперь давайте посчитаем число, обратное к $$$n!$$$ по модулю $$$M$$$. Это можно сделать с помощью бинарного возведения числа $$$n!$$$ в степень $$$M - 2$$$ по модулю $$$M$$$, либо с помощью расширенного алгоритма Евклида.

Теперь мы хотим посчитать массив $$$rf$$$ длины $$$n + 1$$$, где $$$rf_i = \frac{1}{n!}$$$. $$$rf_n$$$ мы посчитали чуть выше, а остальные элементы можно посчитать по формуле $$$rf_i = rf_{i+1} * i\ \%\ M$$$.

Теперь у нас есть посчитанные по модулю $$$M$$$ факториалы и обратные факториалы. Вспоминая, что $$$C_k^n = \frac{n!}{k! \times (n-k)!}$$$, мы можем понять, что $$$C_k^n = f_n \times rf_k \times rf_{n-k}$$$ по модулю $$$M$$$.

Мы научились отвечать на запросы за $$$\mathcal{O}(1)$$$ с предподсчётом за $$$\mathcal{O}(n + \log A)$$$.

Также существует решение за $$$\mathcal{O}(\log n)$$$ на запрос и предподсчётом за $$$\mathcal{O}(n)$$$.

Итоговая асимптотика: $$$\mathcal{O}(n + q + \log A)$$$

#include <bits/stdc++.h>
 
typedef long long ll;
using namespace std;
 
void config_io() {
    ios_base::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
    cout.precision(20);
    cout << fixed;
}
 
const ll MOD = 1e9 + 9, MAX_N = 2e5 + 10;
vector<ll> f(MAX_N + 1);
vector<ll> rf(MAX_N + 1);
 
ll mul(ll a, ll b) {
    return a * b % MOD;
}
 
ll add(ll a, ll b) {
    return (a + b) % MOD;
}
 
ll pow(ll a, ll b) {
    if (b == 0) return 1;
    if (b % 2 == 0) {
        ll v = pow(a, b / 2);
        return mul(v, v);
    }
    return mul(a, pow(a, b - 1));
}
 
ll inv(ll a) {
    return pow(a, MOD - 2);
}
 
ll comb(ll n, ll k) {
    return mul(mul(f[n], rf[n - k]), rf[k]);
}
 
void solve() {
    ll q, n, k;
    cin >> q;
 
    rf[0] = f[0] = 1;
    for (int i = 1; i <= MAX_N; ++i) {
        f[i] = mul(f[i - 1], i);
    }
    rf[MAX_N] = inv(f[MAX_N]);
    for (int i = MAX_N - 1; i > 0; --i) {
        rf[i] = mul(rf[i + 1], i + 1);
    }
 
    for (int i = 0; i < q; ++i) {
        cin >> n >> k;
        cout << comb(n, k) << "\n";
    }
}
 
int main() {
    config_io();
    solve();
    return 0;
}

Существует легенда, которая гласит, что Codeforces работает на хомяках, которые и вырабатывают электричество...

А Вы знали об этом?

Идейным решением данной задачи могли быть следующие ответы: Codeforces, Polygon, MikeMirzayanov.

Регистр написания данных ответов не имел значения :)

print("Codeforces")