Задача «Сдвиги по делителям» — условие и разбор¶

📌 Условие задачи¶

Дана строка s длины n (1 ≤ n ≤ 2⋅10^5), состоящая из строчных латинских букв.
Также дано число k (0 ≤ k ≤ 10^18).

Обозначим через τ(i) количество положительных делителей числа i.

Определим операцию F следующим образом:

Для каждой позиции i (нумерация с 1) в новой строке символ берётся из позиции

f(i) = 1 + ((i - 1 - τ(i)) mod n)

То есть после одного применения операции:

new[i] = old[f(i)]

Необходимо вывести строку, полученную после применения операции F ровно k раз, то есть F^k(s).

💡 Разбор решения¶

1️⃣ Решение «в лоб»¶

Идея¶

Сделаем ровно то, что просит условие:

Для всех i от 1 до n посчитаем τ(i) — количество делителей.
Реализуем один шаг операции F:
для каждой позиции i в новой строке берём символ из f(i)
где f(i) = 1 + ((i - 1 - τ(i)) mod n)
Повторим этот шаг k раз.

Такой подход интуитивный и короткий в коде.

Как посчитать τ(i)¶

Можно использовать «решето по делителям»:

для каждого делителя d пробегаем все кратные d, 2d, 3d, ... и увеличиваем τ(кратного) на 1.

Сложность подсчёта τ:

O(n log n) (точнее, n/1 + n/2 + ... + n/n)

Наивный код на Python (НЕ пройдёт при большом k)¶

def divisors_count_sieve(n: int):
    tau = [0] * (n + 1)
    for d in range(1, n + 1):
        for x in range(d, n + 1, d):
            tau[x] += 1
    return tau

def apply_once(s: str, tau):
    n = len(s)
    t = ['?'] * n
    for i in range(1, n + 1):
        # f(i) = 1 + ((i - 1 - τ(i)) mod n)
        from_pos = 1 + ((i - 1 - tau[i]) % n)
        t[i - 1] = s[from_pos - 1]
    return ''.join(t)

s = input().strip()
k = int(input())
n = len(s)
tau = divisors_count_sieve(n)

for _ in range(k):         # <-- проблема: k до 1e18
    s = apply_once(s, tau)

print(s)

И решение на С++¶

#include <bits/stdc++.h>
using namespace std;

vector<int> divisors_count_sieve(int n) {
    vector<int> tau(n + 1, 0);
    for (int d = 1; d <= n; d++) {
        for (int x = d; x <= n; x += d) tau[x]++;
    }
    return tau;
}

string apply_once(const string& s, const vector<int>& tau) {
    int n = (int)s.size();
    string t(n, '?');
    for (int i = 1; i <= n; i++) {
        // f(i) = 1 + ((i - 1 - τ(i)) mod n)
        long long val = (long long)(i - 1) - (long long)tau[i];
        val %= n;
        if (val < 0) val += n;
        int from_pos = 1 + (int)val;
        t[i - 1] = s[from_pos - 1];
    }
    return t;
}

int main() {
    string s;
    long long k;
    cin >> s >> k;

    int n = (int)s.size();
    auto tau = divisors_count_sieve(n);

    while (k--) {                 // <-- проблема: k до 1e18
        s = apply_once(s, tau);
    }

    cout << s << "\n";
    return 0;
}

Но k может быть до 10^18, поэтому такое решение не подходит.

🔎 Ключевое наблюдение¶

Операция F задаёт перестановку индексов.

Мы фактически определяем массив p, где:

p[i] = f(i)

А один шаг — это:

new[i] = old[p[i]]

После k шагов:

new[i] = old[p^k(i)]

То есть задача сводится к возведению перестановки в степень.

🧮 Алгоритм¶

Посчитать τ(i) для всех i ≤ n
Построить перестановку p
Разложить её на циклы
Для каждого цикла сдвинуть элементы на k mod L

🧩 Мини-пример¶

Возьмём маленький пример:

s = "abcd"
n = 4
k = 1

Шаг 1. Посчитаем τ(i)¶

Количество делителей:

τ(1) = 1
τ(2) = 2
τ(3) = 2
τ(4) = 3

Шаг 2. Найдём f(i)¶

Напомним формулу:

f(i) = 1 + ((i - 1 - τ(i)) mod n)

Посчитаем для каждого i:

i = 1

f(1) = 1 + ((0 - 1) mod 4)
= 1 + (3)
= 4

Значит:

new[1] = old[4]

i = 2

f(2) = 1 + ((1 - 2) mod 4)
= 1 + (3)
= 4

Значит:

new[2] = old[4]

i = 3

f(3) = 1 + ((2 - 2) mod 4)
= 1 + 0
= 1

new[3] = old[1]

i = 4

f(4) = 1 + ((3 - 3) mod 4)
= 1 + 0
= 1


new[4] = old[1]

Шаг 3. Соберём новую строку¶

Исходная строка:

позиции:  1 2 3 4
буквы:    a b c d

По вычислениям:

new[1] = old[4] = d
new[2] = old[4] = d
new[3] = old[1] = a
new[4] = old[1] = a

Получаем:

new = "ddaa"

💡 Что здесь важно заметить?¶

Мы вообще не думаем про "строку" как таковую.
Мы просто:

вычисляем отображение индексов,
подставляем значения.

Если применить операцию ещё раз — мы будем делать то же самое,
но уже к новой строке.

И вот именно в этом месте возникает главный вопрос:

а можно ли понять, что происходит с индексами при многократном применении?

Ответ — да.
Это и приводит к идее перестановок и разложения на циклы.

✨ Красивая идея: разложение на циклы¶

Любая перестановка раскладывается на независимые циклы.

Если цикл имеет длину L, то после k применений:

смещение = k mod L

Внутри цикла нужно просто сделать циклический сдвиг.

Таким образом:

τ(i) считаем за O(n log n) решетом по делителям
Разложение на циклы — O(n)
Итоговая сложность — O(n log n)

k больше не влияет на асимптотику.

🐍 Реализация на Python¶

def divisors_count_sieve(n: int):
    tau = [0] * (n + 1)
    for d in range(1, n + 1):
        for x in range(d, n + 1, d):
            tau[x] += 1
    return tau

def solve():
    s = input().strip()
    k = int(input().strip())
    n = len(s)

    tau = divisors_count_sieve(n)

    # p[i] = откуда берём символ для позиции i
    p = [0] * (n + 1)
    for i in range(1, n + 1):
        p[i] = 1 + ((i - 1 - tau[i]) % n)

    res = ['?'] * n
    used = [False] * (n + 1)

    for start in range(1, n + 1):
        if used[start]:
            continue

        cycle = []
        cur = start
        while not used[cur]:
            used[cur] = True
            cycle.append(cur)
            cur = p[cur]

        L = len(cycle)
        shift = k % L

        for t in range(L):
            to_pos = cycle[t]
            from_pos = cycle[(t + shift) % L]
            res[to_pos - 1] = s[from_pos - 1]

    print(''.join(res))

if __name__ == "__main__":
    solve()

💻 Реализация на C++¶

#include <bits/stdc++.h>
using namespace std;

vector<int> divisors_count_sieve(int n) {
    vector<int> tau(n + 1, 0);
    for (int d = 1; d <= n; d++) {
        for (int x = d; x <= n; x += d) tau[x]++;
    }
    return tau;
}

int main() {

    string s;
    long long k;
    cin >> s >> k;
    int n = (int)s.size();

    auto tau = divisors_count_sieve(n);

    vector<int> p(n + 1);
    for (int i = 1; i <= n; i++) {
        long long val = (long long)(i - 1) - tau[i];
        val %= n;
        if (val < 0) val += n;
        p[i] = 1 + (int)val;
    }

    string res(n, '?');
    vector<char> used(n + 1, 0);

    for (int start = 1; start <= n; start++) {
        if (used[start]) continue;

        vector<int> cycle;
        int cur = start;
        while (!used[cur]) {
            used[cur] = 1;
            cycle.push_back(cur);
            cur = p[cur];
        }

        int L = (int)cycle.size();
        long long shift = k % L;

        for (int t = 0; t < L; t++) {
            int to_pos = cycle[t];
            int from_pos = cycle[(t + shift) % L];
            res[to_pos - 1] = s[from_pos - 1];
        }
    }

    cout << res << "\n";
    return 0;
}

🏁 Итог¶

Главная идея задачи — увидеть не «много раз преобразуем строку», а возведение перестановки в степень через циклы.

Это классический приём:

работает при огромных k
часто встречается в задачах на строки и массивы
превращает невозможное O(n*k) в аккуратное O(n log n)

Уверен, вы встретите подобные задачи ещё не раз.