#P3647. 密码破译

    ID: 2842 传统题 4000ms 128MiB 尝试: 351 已通过: 76 难度: 6 上传者: 标签>难度分类提高字符串周期判定子串哈希双哈希数论线性筛最小质因子预处理CF2100

密码破译

密码破译

题目描述

T64 得到一个由小写英文字母组成的母密码串 ss。每次询问给出 ss 的一个连续片段。对这个片段 SS,找到最短的非空字符串 TT,使得 S=TKS=T^K,即把 TT 连续拼接 KK 次恰好得到 SS,其中 KK 是正整数。

片段 SS 的关键值定义为这个最短的 TT 的长度。求每次询问的关键值。

输入格式

第一行一个正整数 nn。第二行一个长度为 nn 的小写字母串 ss。

第三行一个正整数 mm,表示询问次数。随后 mm 行,每行两个整数 L,RL,R,表示从第 LL 个到第 RR 个字符的闭区间,1≤L≤R≤n1\le L\le R\le n。

输出格式

每次询问输出一行一个正整数。

6
aababa
3
1 3
1 2
2 6
3
1
5

数据范围

1≤n≤5000001\le n\le500000,1≤m≤20000001\le m\le2000000。