#ifndef LOCAL
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2")
#endif

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

using ll = long long;
using ld = long double;

#define all(a) begin(a), end(a)
#define len(a) int((a).size())

struct suffix_array {
    std::vector<int> order, suffix_position, lcp;

    template<typename T>
    suffix_array(T str = T()) {
        str.push_back(*std::min_element(str.begin(), str.end()) - 1);
        int n = str.size();

        order.resize(n);
        std::iota(order.begin(), order.end(), 0);
        std::sort(order.begin(), order.end(), [&](const int i, const int j) {
            return str[i] < str[j];
        });

        suffix_position.resize(n);
        for (int i = 0; i < n; i++)
            suffix_position[order[i]] = i == 0 ? 0 : suffix_position[order[i - 1]] + (str[order[i]] != str[order[i - 1]]);

        std::vector<int> ptr(n), new_order(n), new_suffix_position(n);
        for (int len = 1; suffix_position[order.back()] != n - 1; len <<= 1) {
            std::fill(ptr.begin(), ptr.begin() + suffix_position[order.back()] + 1, 0);
            for (int i = 0; i < n; i++)
                if (suffix_position[i] + 1 < n)
                    ptr[suffix_position[i] + 1]++;

            for (int i = 1; i <= suffix_position[order.back()]; i++)
                ptr[i] += ptr[i - 1];

            for (const int position : order) {
                int suffix = (position - len + n) % n;
                new_order[ptr[suffix_position[suffix]]++] = suffix;
            }
            std::swap(order, new_order);

            for (int i = 0; i < n; i++)
                new_suffix_position[order[i]] = i == 0 ? 0 : new_suffix_position[order[i - 1]]
                + (suffix_position[order[i]] != suffix_position[order[i - 1]]
                || suffix_position[(order[i] + len) % n] != suffix_position[(order[i - 1] + len) % n]);

            std::swap(suffix_position, new_suffix_position);
        }
        assert(order[0] == n - 1);

        lcp.resize(n);
        int current_lcp = 0;
        for (int suffix = 0; suffix < n - 1; suffix++, current_lcp = current_lcp == 0 ? 0 : current_lcp - 1) {
            int previous_suffix = order[suffix_position[suffix] - 1];
            while (str[suffix + current_lcp] == str[previous_suffix + current_lcp])
                current_lcp++;

            lcp[suffix_position[suffix]] = current_lcp;
        }
    }
};

constexpr int N = 1e5 + 228;
constexpr int STEP = 20;
constexpr int BLOCKS = N / STEP + 1;
constexpr int MASK = 1 << STEP;
int ppc[MASK], prec[MASK];

void precalc() {
    for (int mask = 0; mask < MASK; mask++) {
        ppc[mask] = __builtin_popcount(mask);
        for (int i = 0; i < STEP; i++) {
            if (mask >> i & 1) {
                prec[mask] += i + 1;
            }
        }
    }
}

struct custom_bitset {
    int block[BLOCKS];

    custom_bitset(int ones = 0) {
        memset(block, 0, sizeof(block));
        int pos = 0;
        while (pos + STEP <= ones) {
            block[pos / STEP] = (1 << STEP) - 1;
            pos += STEP;
        }
        while (pos < ones) {
            set(pos, 1);
            pos++;
        }
    }

    void set_and(const custom_bitset &other) {
        for (int i = 0; i < BLOCKS; i++) {
            block[i] &= other.block[i];
        }
    }

    void set_or(const custom_bitset &other) {
        for (int i = 0; i < BLOCKS; i++) {
            block[i] |= other.block[i];
        }
    }

    void set(int pos, int val) {
        int id = pos / STEP;
        int rel = pos % STEP;
        if (val == 1) {
            block[id] |= 1 << rel;
        } else {
            block[id] &= ~(1 << rel);
        }
    }

    int get(int i) {
        int id = i / STEP;
        int rel = i % STEP;
        return block[id] >> rel & 1;
    }

    ll solve() {
        ll ans = 0;
        for (int i = 0; i < BLOCKS; i++) {
            ans += 1ll * ppc[block[i]] * (i * STEP) + prec[block[i]];
        }
        // for (int i = 0; i < N; i++) {
        //     if (get(i)) {
        //         ans += i + 1;
        //     }
        // }
        return ans;
    }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    precalc();

    int n;
    string s;
    cin >> n >> s;
    suffix_array sa(s);

    int B = 1;
    while (B * B <= n) {
        B++;
    }

    vector<int> sieve(B);
    iota(all(sieve), 0);
    vector<custom_bitset> coprime(B);
    for (int x = 2; x < B; x++) {
        if (sieve[x] != x) {
            continue;
        }
        for (int y = x; y < B; y += x) {
            sieve[y] = min(sieve[y], x);
        }
        coprime[x] = custom_bitset(n);
        for (int i = 0; i < n; i += x) {
            coprime[x].set(i, 0);
        }
    }

    custom_bitset killed;

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        killed.set_and(custom_bitset(sa.lcp[i]));

        int left = sa.order[i] + 1;
        custom_bitset cpr(n - left + 1);
        for (int x = 2; x < B; x++) {
            if (left % x != 0) {
                continue;
            }
            cpr.set_and(coprime[x]);
            while (left % x == 0) {
                left /= x;
            }
        }
        if (left > 1) {
            for (int x = 0; x < n - left + 1; x += left) {
                cpr.set(x, 0);
            }
        }

        auto prev = cpr;
        ans += cpr.solve();
        cpr.set_and(killed);
        ans -= cpr.solve();
        killed.set_or(prev);
    }
    cout << ans << '\n';
}

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:6:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::__cxx11::basic_string<char>::_Alloc_hider::~_Alloc_hider()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = char]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/string:54:
/usr/include/c++/13/bits/basic_string.h:181:14: note: called from here
  181 |       struct _Alloc_hider : allocator_type // TODO check __is_final
      |              ^~~~~~~~~~~~