Идея: AndreyPavlov
Подготовка: AndreyPavlov
Разбор: AndreyPavlov
Заметим, что существует два варианта какие числа брать, чтобы их сумма была нечётной: $$$3$$$ нечетных числа; $$$2$$$ четных и $$$1$$$ нечетное. Сохраним все индексы четных и нечетных чисел в два массива, и проверим оба случая.
def solve():
n = int(input())
a = list(map(int, input().split()))
odd, even = [], []
for i in range(n):
if a[i] % 2 == 0:
even.append(i + 1)
else:
odd.append(i + 1)
if len(odd) >= 1 and len(even) >= 2:
print("YES")
print(odd[0], even[0], even[1])
elif len(odd) >= 3:
print("YES")
print(odd[0], odd[1], odd[2])
else:
print("NO")
t = int(input())
for test in range(t):
solve()
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> odd, even;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (x % 2 == 0) {
even.push_back(i);
} else {
odd.push_back(i);
}
}
if (odd.size() >= 3) {
cout << "YES\n";
cout << odd[0] << " " << odd[1] << " " << odd[2] << '\n';
} else if (odd.size() >= 1 && even.size() >= 2) {
cout << "YES\n";
cout << odd[0] << " " << even[0] << " " << even[1] << '\n';
} else {
cout << "NO\n";
}
}
}
Идея: 74TrAkToR
Подготовка: qualdoom
Разбор: qualdoom
Давайте заметим, что нам не имеет смысла разбивать больше, чем на $$$k = 2$$$ подотрезков. Докажем это.
Пусть мы как — то разбили массив $$$a$$$ на $$$m > 2$$$ подотрезков : $$$b_1, b_2, \ldots, b_m$$$. Заметим, что $$$\gcd(b_1, b_2, \ldots, b_m) \le \gcd(b_1 + b_2, b_3, \ldots, b_m)$$$, так как если $$$b_1$$$ и $$$b_2$$$ были кратны $$$\gcd(b_1, b_2 , \ldots, b_m)$$$, значит и $$$b_1 + b_2$$$ тоже кратно $$$\gcd(b_1, b_2, \ldots, b_m)$$$. А значит, мы можем вместо $$$b_1$$$ и $$$b_2$$$ использовать $$$b_1 + b_2$$$, и ответ не ухудшится, таким образом, всегда выгодно использовать не более $$$k = 2$$$ подотрезков.
Как найти ответ? Пусть $$$s$$$ — сумма массива $$$a$$$. Давайте допустим $$$pref_i = {\sum_{j = 1}^{i} a_j}$$$, тогда ответ это $$$\max\limits_{1 \le i < n}(\gcd(pref_i, s - pref_i)$$$.
from math import gcd
t = int(input())
for test in range(t):
n = int(input())
a = list(map(int, input().split()))
s = 0
for i in range(n):
s += a[i]
ans = 0
pref = 0
for i in range(n - 1):
pref += a[i]
ans = max(ans, gcd(pref, s - pref))
print(ans)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T = 1;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
long long s = accumulate(a.begin(), a.end(), 0ll), cur = 0;
long long ans = 1;
for (int i = 0; i < n - 1; i++) {
cur += a[i], s -= a[i];
ans = max(ans, __gcd(s, cur));
}
cout << ans << "\n";
}
}
Идея: AndreyPavlov
Подготовка: qualdoom, AndreyPavlov
Разбор: qualdoom, AndreyPavlov
У этой задачи есть два похожих решения, мы расскажем оба.
Вычтем $$$1$$$. Что теперь можно сказать о количестве единиц в начале двоичной записи числа? Их ровно $$$cnt - cnt_w + 1$$$, где $$$cnt$$$ — количество единичных битов после вычитания единички, а $$$cnt_w$$$ — до вычитания. Теперь вычтем их, для этого нужно вычесть число $$$2^{cnt - cnt_w - 1} + 1$$$ и продолжим алгоритм. Но такой алгоритм делает в худшем $$$60$$$ запросов. Чтобы сэкономить запросы заметим, что мы знаем количество единиц после того, как уберем единицы с начала, следовательно делать ещё один запрос для этого бесполезно. Тогда вместе с тем, как уберем единицы с начала, вычтем сразу и единичку. По итогу будет совершенно не более $$$cnt$$$ операций, где $$$cnt$$$ — изначальное количество единичных битов в записи числа $$$n$$$. Это число не превосходит $$$O(log_2 (n))$$$, в свою очередь $$$log_2 (n)$$$ не превосходит 30, что укладывается в ограничения.
Пусть $$$ans$$$ — искомое число $$$n$$$, а $$$was$$$ — изначальное количество битов в числе $$$n$$$. Давайте вычитать степени двойки : $$$2^0, 2^1, 2^2, ... 2^k$$$, пока $$$was$$$ не станет 0. Будем поддерживать флаг $$$Shift$$$ — был ли перенос битов в $$$n$$$ при вычитании какой — либо степени двойки. Пусть мы вычли на $$$k$$$-м шаге $$$2^k$$$ и количество битов стало равно $$$cnt_{new}$$$, а до вычитания было $$$cnt$$$, тогда рассмотрим два случая.
1) $$$cnt - cnt_{new} = 1$$$, тогда бит $$$k$$$ был включен в $$$n$$$ на $$$k$$$ — ом шаге, и если $$$Shift = false$$$, то прибавим к $$$ans$$$ — $$$2^k$$$, так как не было переноса битов, а значит бит k есть и в изначальном числе, и вычтем из $$$was$$$ — $$$1$$$. Если $$$Shift = true$$$, то мы этот бит добавили при предыдущих операциях, и его учитывать не нужно.
2) $$$cnt - cnt_{new} \neq 1$$$, тогда мы знаем, что кол-во битов не уменьшилось, также, что в числе $$$n$$$ нашелся такой бит $$$m$$$, что $$$2^m > 2^k$$$, и при этом бит $$$m$$$ есть в $$$n$$$. Причем $$$m - k - 1 = cnt_{new} - cnt$$$. Значит $$$m = k + 1 + cnt_{new} - cnt$$$. Давайте прибавим к ответу $$$2^m$$$, вычтем из $$$was$$$ — $$$1$$$ и присвоим флагу $$$Shift$$$ значение $$$true$$$, так как был перенос битов.
Таким образом, мы нашли изначальное число $$$n$$$, которое равно $$$ans$$$, а также сделали не более $$$O(log_2(n))$$$ запросов, так как $$$k \le log_2(n)$$$.
Таким образом, решение тратит не более 30 запросов, что укладывается в ограничения задачи.
t = int(input())
def ask (x):
print('-', x)
return int(input())
for i in range(t):
cur = int(input())
add = 0
ans = 0
while cur > 0:
x = ask(add + 1)
back = x - cur + 1
add = 2 ** back - 1
ans += 2 ** back
cur = x - back
print('!', ans)
#include <iostream>
using namespace std;
int ask (int x) {
cout << "- " << x << endl;
if (x == -1)
exit(0);
cin >> x;
return x;
}
int main() {
int t;
cin >> t;
while (t--) {
int cnt;
cin >> cnt;
int n = 0;
int was = 0;
while (cnt > 0) {
n += 1;
int nw = ask(1 + was);
int back = nw - cnt + 1;
n += (1 << back) - 1;
was = (1 << back) - 1;
cnt = nw - back;
}
cout << "! " << n << endl;
}
}
1780E - Josuke and Complete Graph
Идея: IzhtskiyTimofey
Подготовка: IzhtskiyTimofey
Разбор: IzhtskiyTimofey
Давайте зафиксируем $$$g$$$ и проверим, что ребро веса $$$g$$$ существует в $$$G'$$$. Первое число, которое делится на $$$g$$$, начиная с $$$L$$$ — $$$\lceil \frac{L}{g} \rceil \cdot g$$$, а второе — $$$(\lceil \frac{L}{g} \rceil + 1) \cdot g$$$, заметим что их $$$gcd$$$ равен $$$g$$$, то есть ребро между этими вершинами имеет вес $$$g$$$. Если второе число больше $$$R$$$, то ребра веса $$$g$$$ в графе $$$G'$$$ не существует, потому что на отрезке с $$$L$$$ по $$$R$$$ максимум только одна вершина, которая делится на $$$g$$$. То есть надо посчитать количество таких $$$g$$$, что $$$(\lceil \frac{L}{g} \rceil + 1) \cdot g \leq R$$$.
Рассмотрим $$$g \geq L$$$, тогда $$$(\lceil \frac{L}{g} \rceil + 1) \cdot g = 2 \cdot g$$$. Получаем верхнее ограничение на $$$g \leq \lfloor \frac{R}{2} \rfloor$$$. То есть $$$L \leq g \leq \lfloor \frac{R}{2} \rfloor$$$ — удовлетворяют.
Остались $$$g < L$$$.
Заметим, что $$$\lceil \frac{L}{g} \rceil$$$ принимает $$$O(\sqrt{L})$$$ значений. Тогда зафиксируем какое-то $$$f = \lceil \frac{L}{g} \rceil$$$, заметим, что $$$f$$$ соответствует последовательный отрезок значений $$$l \leq g \leq r$$$. Будем перебирать такие отрезки, поскольку их столько же, сколько и различных значений $$$f$$$, то есть $$$O(\sqrt{L})$$$. Тогда, если есть левая граница отрезка $$$l$$$, можно найти $$$r$$$ либо бинарным поиском, либо расписать формулу. Следующая левая граница будет просто $$$r + 1$$$. Тогда заметим, что если зафиксировано $$$f$$$, то $$$(f + 1) \cdot g \leq R$$$ равноценно $$$g \leq \lfloor \frac{R}{f + 1} \rfloor$$$. То есть при фиксированном отрезке с $$$l$$$ по $$$r$$$, $$$g$$$ удовлетворяет ограничению $$$l \leq g \leq min(r, \lfloor \frac{R}{f + 1} \rfloor)$$$. Тогда переберем все такие отрезки и просуммируем по ним хорошие $$$g$$$.
Тогда получается решение за $$$O(\sqrt{L})$$$ или $$$O(\sqrt{L} \cdot log(L))$$$, что, если аккуратно написать, тоже проходит.
def solve():
L, R = map(int, input().split())
ans = max(0, R // 2 - L + 1)
left = 1
while left < L:
C = (L + left - 1) // left
right = (L + C - 2) // (C - 1) - 1
ans += max(0, min(right, R // (C + 1)) - left + 1)
left = right + 1
print(ans)
t = int(input())
for test in range(t):
solve()
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
for (int test_case = 0; test_case < t; test_case++){
ll L, R;
cin >> L >> R;
ll ans = max(0ll, R / 2 - L + 1);
for (ll left = 1, right; left < L; left = right + 1){
ll C = (L + left - 1) / left;
right = (L + C - 2) / (C - 1) - 1;
ans += max(0ll, min(right, R / (C + 1)) - left + 1);
}
cout << ans << '\n';
}
}
Идея: AndreyPavlov
Подготовка: AndreyPavlov
Разбор: qualdoom
Отсортируем массив и будем обрабатывать тройки $$$i, j, k$$$, считая что $$$i < j < k$$$ и $$$a_i < a_j < a_k$$$. Теперь если $$$gcd(a_i, a_k) = 1$$$, то количество способов взять индекс $$$j$$$ равно $$$k - i - 1$$$.
Будем считать ответ на задачу для каждого $$$k$$$ от $$$1$$$ до $$$n$$$, считая что $$$a_k$$$ — максимальное число в тройке. Теперь пусть $$$c$$$ — количество чисел, взаимно простых с $$$a_k$$$ на префиксе от $$$1$$$ до $$$k - 1$$$, а $$$sum$$$ — сумма их индексов. Тогда к ответу нужно прибавить $$$c \cdot i - sum - c$$$.
Осталось узнавать количество чисел, взаимно простых с $$$a_k$$$ и сумму их индексов. Это можно делать с помощью метода включений и исключений. Пусть $$$cnt_i$$$ — количество чисел $$$a_j$$$, которые делятся на $$$i$$$, $$$s_i$$$ — сумма индексов $$$j$$$ чисел $$$a_j$$$, которые делятся на $$$i$$$. Посмотрим на простые числа $$$p_1, p_2, ..., p_m$$$, входящие в факторизацию числа $$$a_k$$$.
Тогда пусть изначально $$$c$$$ равно количеству чисел на префиксе, а $$$sum$$$ сумме индексов на префиксе. Заметим, что тогда мы учли лишние элементы — числа, которые делятся на $$$p_1, p_2, ..., p_m$$$, так как они будут не взаимно просты с $$$a_k$$$, вычтем их из $$$c$$$ и $$$sum$$$. Но сделав это мы опять же учли лишние элементы, кратные числам вида $$$p_i * p_j$$$, где $$$i \neq j$$$, прибавим их обратно и т.д. Таким образом мы можем перебрать маску $$$mask$$$ простых чисел $$$p_1, p_2, ..., p_m$$$. И в зависимости от четности битов в маске будем вычитать или прибавлять элементы, кратные $$$d$$$, , где $$$d$$$ — произведение простых, входящих в $$$mask$$$. Получив $$$c$$$ и $$$sum$$$ мы можем пересчитать ответ для позиции $$$i$$$.
Чтобы перейти от позиции $$$i$$$ к позиции $$$i+1$$$, обновим значения $$$cnt$$$ и $$$s$$$, добавив элемент $$$a_{i-1}$$$ с помощью перебора маски простых элемента $$$a_{i-1}$$$.
#include "bits/stdc++.h"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define sz(v) ((int)(v).size())
#define all(a) (a).begin(), (a).end()
#define rall(a) a.rbegin(), a.rend()
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define time ((double)clock() / (double)CLOCKS_PER_SEC)
using pii = pair<int, int>;
using ll = long long;
using int64 = long long;
using ld = double;
const ll infll = (ll) 1e18 + 27;
const ll inf = (ll) 1e9;
#define dbg(x) cout << #x << " = " << (x) << endl
template<class T>
using pq = priority_queue<T, vector<T>, less<T>>;
template<class T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename T2>
istream &operator>>(istream &in, pair<T, T2> &b) {
in >> b.first >> b.second;
return in;
}
template<typename T, typename T2>
ostream &operator<<(ostream &out, const pair<T, T2> &b) {
out << "{" << b.first << ", " << b.second << "}";
return out;
}
template<typename T>
istream &operator>>(istream &in, vector<T> &b) {
for (auto &v : b) {
in >> v;
}
return in;
}
template<typename T>
ostream &operator<<(ostream &out, vector<T> &b) {
for (auto &v : b) {
out << v << ' ';
}
return out;
}
template<typename T>
ostream &operator<<(ostream &out, deque<T> &b) {
for (auto &v : b) {
out << v << ' ';
}
return out;
}
template<typename T>
void print(T x, string end = "\n") {
cout << x << end;
}
template<typename T1, typename T2>
bool chkmin(T1 &x, const T2 &y) { return x > y && (x = y, true); }
template<typename T1, typename T2>
bool chkmax(T1 &x, const T2 &y) { return x < y && (x = y, true); }
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N = 3e5 + 10;
ll s[N];
ll cnt[N];
ll d[N][20];
int ptr[N];
bool u[N];
ll Cnt = 0;
ll Sum = 0;
ll Ans = 0;
void Answer (int x, int pos) {
ll C = Cnt;
ll X = Sum;
int K = (1ll << ptr[x]);
for (int mask = 1; mask < K; mask++) {
ll k = 1;
for (int j = 0; j < ptr[x]; j++) {
if ((mask >> j) & 1) {
k *= d[x][j];
}
}
int bits = __builtin_popcount(mask);
int D = k;
if (bits % 2 == 1) {
C -= cnt[D];
X -= s[D];
} else {
C += cnt[D];
X += s[D];
}
}
Ans += C * pos - X;
}
void add (int x, int pos) {
Cnt += 1;
Sum += pos + 1;
auto v = d[x];
int K = (1ll << ptr[x]);
for (int mask = 1; mask < K; mask++) {
ll k = 1;
for (int j = 0; j < ptr[x]; j++) {
if ((mask >> j) & 1) {
k *= d[x][j];
}
}
int D = k;
s[D] += pos + 1;
cnt[D] += 1;
}
}
void solve() {
for (int i = 2; i < N; i++) {
if (!u[i]) {
for (int j = i; j < N; j += i) {
u[j] = true;
d[j][ptr[j]] = i;
ptr[j]++;
}
}
}
int n;
cin >> n;
vector<int> a(n);
cin >> a;
sort(all(a));
for (int i = 0; i < n; i++) {
Answer(a[i], i);
if (i > 0) {
add(a[i - 1], i - 1);
}
}
cout << Ans << "\n";
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
solve();
return 0;
}
Идея: IzhtskiyTimofey
Подготовка: IzhtskiyTimofey, AndreyPavlov
Разбор: IzhtskiyTimofey, AndreyPavlov
Эта задача имеет несколько решений, использующих разные суффиксные структуры. Мы расскажем два из них — использующее суффиксный массив, и использующее суффиксный автомат.
Для начала построим суффиксный массив $$$suf$$$ и массив $$$lcp$$$ (наибольших общих префиксов) на строке $$$s$$$. Зафиксируем какое-то $$$k > 1$$$ и будем рассматривать все подстроки строки $$$s$$$ длины $$$k$$$. Сопоставим $$$1$$$ позициям $$$i$$$ массива $$$lcp$$$, таким что $$$lcp_i \geq k$$$, а остальным позициям $$$0$$$. Единица в позиции $$$i$$$ означает, что подстроки длины $$$k$$$, начинающиеся $$$suf_i$$$ и $$$suf_{i + 1}$$$, равны. Рассмотрим какой-то блок длины $$$len$$$ из единиц, тогда для $$$len + 1$$$ подстрок длины $$$k$$$ количество вхождений в $$$s$$$ — $$$len + 1$$$, тогда чтобы подстроки в этом блоке были вкусными, надо, чтобы $$$len + 1$$$ делилось на $$$k$$$.
Будем перебирать $$$k$$$ от $$$n$$$ до $$$2$$$ и поддерживать все размеры блоков. Тогда, при переходе к новому $$$k$$$ необходимо поддерживать события — изменить $$$0$$$ на $$$1$$$, в таких $$$i$$$, что $$$lcp_i = k$$$. Чтобы это делать, можно поддерживать СНМ. Тогда, когда мы знаем для каждого размера — количество блоков с таким размером, достаточно рассмотреть все блоки длины $$$len$$$, такие что $$$len + 1$$$ — делитель $$$k$$$. Это можно делать явно, перебирая $$$k$$$, $$$2 \cdot k$$$, ..., поскольку, это будет работать за сумму гармонического ряда.
Для $$$k = 1$$$, очевидно, что любые подстроки длины $$$1$$$ подходят, поэтому можно просто добавить к ответу $$$n$$$. Итоговая асимптотика $$$O(n \cdot log(n))$$$
Построим сам суффиксный автомат, теперь насчитаем для каждой вершины суффиксного автомата динамику $$$dp_v$$$ — это количество путей из вершины $$$v$$$ в терминальные вершины. Эта динамика означает количество вхождений подстроки, соответствующей этой вершине, во всю строку. Введём функцию $$$f(v)$$$ — длина самой длинной подстроки ведущей в вершину $$$v$$$. Мы знаем, что в вершину $$$v$$$ суффиксного автомата ведут все подстроки длиной от $$$l_v$$$ до $$$r_v$$$ — каждая единожды. Где $$$r_v = f(v)$$$, а $$$l_v = f(suff_v) + 1$$$, где $$$suff_v$$$ — суффиксная ссылка вершины $$$v$$$. Почему это так? В вершину $$$v$$$ суффиксного автомата ведут все подстроки вида $$$s[x:k], s[x+1:k], ..., s[y:k]$$$, а есть суффиксная ссылка $$$suff_v$$$, в которую ведут все подстроки вида $$$s[x + 1:k], s[y + 2:k], ..., s[t: k]$$$.
Для того чтобы решить задачу переберём вершину $$$v$$$ и посмотрим на количество вхождений любой подстроки которая ведёт в вершину $$$v$$$ — $$$dp_v$$$, тогда зафиксируем $$$c$$$ — количество таких $$$l_v \le x \le r_v$$$, что $$$dp_v$$$ делится нацело на $$$x$$$. Следовательно к ответу нужно прибавить $$$dp_v \cdot c$$$. Все делители можно сохранить за $$$O(n \cdot log(n))$$$ и каждый раз искать бинпоиском количество таких $$$x$$$.
Асимптотика $$$O(n \cdot log(n))$$$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> suffix_array(string s){
int n = s.size();
vector<int> a(n), c(n), h(n);
vector<pair<char, int>> t;
for (int i = 0; i < n; i++) t.push_back({s[i], i});
sort(t.begin(), t.end());
int cur = -1;
for (int i = 0; i < n; i++){
if (i == 0 || t[i].first != t[i - 1].first){
cur++;
h[cur] = i;
}
a[i] = t[i].second;
c[a[i]] = cur;
}
vector<int> a1(n), c1(n);
for (int len = 1; len < n; len *= 2){
for (int i = 0; i < n; i++){
int j = (n + a[i] - len) % n;
a1[h[c[j]]++] = j;
}
a = a1;
cur = -1;
for (int i = 0; i < n; i++){
if (i == 0 || c[a[i]] != c[a[i - 1]] || c[(a[i] + len) % n] != c[(a[i - 1] + len) % n]){
cur++;
h[cur] = i;
}
c1[a[i]] = cur;
}
c = c1;
}
return a;
}
vector<int> build_lcp(string s, vector<int> suf){
int n = s.size();
vector<int> rsuf(n), lcp(n);
for (int i = 0; i < n; i++) rsuf[suf[i]] = i;
int cur = 0;
for (int i = 0; i < n; i++){
int j = rsuf[i];
if (j != n - 1){
while (s[suf[j] + cur] == s[suf[j + 1] + cur]) cur++;
lcp[j] = cur;
}
if (cur > 0) cur--;
}
return lcp;
}
const int N = 1e6 + 1;
int r[N], l[N], us[N], cnt[N];
vector<int> pos[N];
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int n;
cin >> n;
string s;
cin >> s;
s += '$';
vector<int> suf = suffix_array(s);
vector<int> lcp = build_lcp(s, suf);
for (int i = 0; i < lcp.size(); i++) {
pos[lcp[i]].push_back(i);
}
ll ans = n;
for (int k = n; k >= 2; k--) {
for (int i : pos[k]) {
// add i
us[i] = true;
cnt[1]++;
l[i] = r[i] = i;
if (i != 0 && us[i - 1]) {
cnt[i - l[i - 1]]--;
cnt[1]--;
cnt[i - l[i - 1] + 1]++;
l[i] = l[i - 1];
r[l[i - 1]] = i;
}
if (i + 1 < lcp.size() && us[i + 1]) {
cnt[r[i + 1] - i]--;
cnt[i - l[i] + 1]--;
cnt[r[i + 1] - l[i] + 1]++;
l[r[i + 1]] = l[i];
r[l[i]] = r[i + 1];
}
}
for (int x = k; x <= n; x += k) {
ans += 1ll * x * cnt[x - 1];
}
}
cout << ans << "\n";
}
/* Includes */
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
/* Using libraries */
using namespace std;
/* Defines */
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ld long double
#define pb push_back
#define vc vector
#define sz(a) (int)a.size()
#define forn(i, n) for (int i = 0; i < n; ++i)
#define pii pair <int, int>
#define vec pt
#define all(a) a.begin(), a.end()
const int K = 26;
const int N = 1e6 + 1;
struct node {
int next[K];
int suf = -1, pr = -1, dp = 0, len = 0, ch = -1;
node () {
forn (i, K) next[i] = -1;
}
};
int get (char c) {
if (c >= 'a')
return c - 'a';
return c - 'A';
}
int lst = 0, sz = 1;
node t[N * 2];
int used[N * 2];
int add (int a, int x) {
int b = sz++;
t[b].pr = a;
t[b].suf = 0;
t[b].ch = x;
for (; a != -1; a = t[a].suf) {
if (t[a].next[x] == -1) {
t[a].next[x] = b;
t[b].len = max(t[b].len, t[a].len + 1);
continue;
}
int c = t[a].next[x];
if (t[c].pr == a) {
t[b].suf = c;
break;
}
int d = sz++;
forn (i, K) t[d].next[i] = t[c].next[i];
t[d].suf = t[c].suf;
t[c].suf = t[b].suf = d;
t[d].pr = a;
t[d].ch = x;
for (; a != -1 && t[a].next[x] == c; a = t[a].suf) {
t[a].next[x] = d;
t[d].len = max(t[d].len, t[a].len + 1);
}
break;
}
return b;
}
void add (char c) {
lst = add(lst, get(c));
}
void dfs (int u) {
used[u] = 1;
for (int i = 0; i < K; ++i) {
if (t[u].next[i] == -1) continue;
int v = t[u].next[i];
if (!used[v])
dfs(v);
t[u].dp += t[v].dp;
}
}
vc <int> p[N], pr;
int dr[N];
vc <pii> d;
int l, r, cur = 0;
int cnt_log (int x, int y) {
int z = 1, res = 0;
while (y >= z) {
z *= x;
++res;
}
return res - 1;
}
void rec (int i, int x) {
if (i == sz(d)) {
cur += l <= x;
return;
}
rec(i + 1, x);
for (int j = 1; j <= d[i].second; ++j) {
x *= d[i].first;
if (x > r)
break;
rec(i + 1, x);
}
}
void solve () {
int n;
cin >> n;
string s;
cin >> s;
for (char c : s)
add(c);
for (int a = lst; a != -1; a = t[a].suf)
t[a].dp = 1;
dfs(0);
for (int i = 2; i <= n; ++i) {
if (dr[i] == 0) {
dr[i] = i;
pr.pb(i);
}
for (int j = 0; j < sz(pr) && pr[j] <= dr[i] && i * pr[j] <= n; ++j)
dr[i * pr[j]] = pr[j];
}
long long ans = 0;
forn (i, sz) {
if (t[i].len == 0) continue;
l = t[t[i].suf].len + 1;
r = t[i].len;
int x = t[i].dp;
d.clear();
while (x > 1) {
int y = dr[x];
if (d.empty() || d.back().first != y)
d.pb({y, 1});
else
d.back().second++;
x /= y;
}
rec(0, 1);
ans += t[i].dp * cur;
cur = 0;
}
cout << ans << '\n';
}
/* Starting and precalcing */
signed main() {
/* freopen("input.txt","r",stdin);freopen("output.txt","w",stdout); */
fast;
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}