2795: [Poi2012]A Horrible Poem
Time Limit: 50 Sec Memory Limit: 128 MB
Submit: 1235 Solved: 595
[Submit][Status][Discuss]
Description
给出一个由小写英文字母组成的字符串S，再给出q个询问，要求回答S某个子串的最短循环节。
如果字符串B是字符串A的循环节，那么A可以由B重复若干次得到。
Input
第一行一个正整数n (n<=500,000)，表示S的长度。
第二行n个小写英文字母，表示字符串S。
第三行一个正整数q (q<=2,000,000)，表示询问个数。
下面q行每行两个正整数a,b (1<=a<=b<=n)，表示询问字符串S[a..b]的最短循环节长度。
Output
依次输出q行正整数，第i行的正整数对应第i个询问的答案。
Sample Input
8
aaabcabc
3
1 3
3 8
4 8
Sample Output
1
3
5
HINT
Source
鸣谢 jiangzoi&oimaster
[Submit][Status][Discuss]
分析：
此题关键是如何加快询问速度。
1、循环节一定是区间长度的约数。
2、如果n是一个循环节，那么k*n也必定是一个循环节（关键所在）
3、n是[l,r]这一段的循环节 的充要条件是 [l,r-n]和[l+n,r]相同（利用这个性质我们在判断是否为循环姐是可以做到O(1)）
字符串Hash来完成第三步，但第一步枚举约数会超时，因为这题卡常数，所以需要用质因数分解来优化，具体如下，用一个minp来记录x的i的最小质因数，然后利用递归可以求出x的质因数fac，x=fac1*fac2*fac3……且非降序，（具体实现看代码），x/最小的质因数=最大的约数（出来x自己），比如12=2*2*3，6=12/2，如果6不行，那么2和3和1也不行，利用第二步优化一下。
#include<bits/stdc++.h>
using namespace std;
const int N=500010;
const int P=131;
typedef unsigned long long ULL;
typedef long long LL;
char str[N];
int n;
ULL hashv[N],power[N];
void calHash()
{power[0]=1;for(int i=1; i<=n; i++){hashv[i]=hashv[i-1]*P+(str[i]-'a'+1 );power[i]=power[i-1]*P;}
}
typedef long long ll;
ll prime[N] = {0},num_prime = 0; //prime存放着小于N的素数
int isNotPrime[N] = {1, 1}; // isNotPrime[i]如果i不是素数，则为1
ll minp[N];//i的最小质因数
int Prime()
{for(ll i = 2 ; i < N ; i ++){if(! isNotPrime[i]){prime[num_prime ++]=i;minp[i]=i;}//无论是否为素数都会下来for(ll j = 0 ; j < num_prime && i * prime[j] < N ; j ++){isNotPrime[i * prime[j]] = 1;minp[i*prime[j]]=prime[j];if( !(i % prime[j] ) ) //遇到i最小的素数因子//关键处1break;}}return 0;
}bool judge(int l,int r,int len)
{return hashv[r-len]-hashv[l-1]*power[r-len-l+1]==hashv[r]-hashv[l+len-1]*power[r-len-l+1];
}
int fac[N];int main()
{scanf("%d",&n);scanf("%s",str+1);calHash();Prime();int q;scanf("%d",&q);while(q--){int l,r;scanf("%d%d",&l,&r);int len=r-l+1;//x=p1*p2*....求出p1，p2 ，且保证不降int num=0;while(len!=1){fac[++num]=minp[len];len=len/minp[len];}len=r-l+1; for(int i=1;i<=num;i++){//cout<<len/fac[i]<<endl;if(judge(l,r,len/fac[i]))len/=fac[i];}printf("%d\n",len);}return 0;}