首页 > > 程序设计 > C/C++ >

Common Divisors CodeForces - 182D || kmp最小…

2018-06-17 21:55:13来源：未知阅读 ()

Common Divisors CodeForces - 182D

思路：用kmp求next数组的方法求出两个字符串的最小循环节长度（http://blog.csdn.net/acraz/article/details/47663477，http://www.cnblogs.com/chenxiwenruo/p/3546457.html），然后取出最小循环节，如果最小循环节不相同答案就是0，否则求出各个字符串含有的最小循环节的数量，求这两个数量的公因数个数（也就是最大公因数的因子个数）就是答案。

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<cstring>
 4 char s1[100010],s2[100010];
 5 char c[100010],d[100010];
 6 int f[100010];
 7 int m1,m2,ans;
 8 int getf(char *P,int *f,int& m)
 9 {
10     int j=f[0]=-1,i=0;
11     while(i<m)
12     {
13         while(j>=0&&P[i]!=P[j])    j=f[j];
14         ++j;++i;
15         f[i]=j;
16     }
17     return m%(m-f[m])==0?m-f[m]:m;
18 }
19 int gcd(int a,int b)
20 {
21     int t;
22     while(b!=0)
23     {
24         t=a;
25         a=b;
26         b=t%b;
27     }
28     return a;
29 }
30 int main()
31 {
32     int i,p,t;
33     scanf("%s%s",s1,s2);
34     m1=strlen(s1);
35     m2=strlen(s2);
36     int a=getf(s1,f,m1);
37     int b=getf(s2,f,m2);
38     strncpy(c,s1,a);
39     strncpy(d,s2,b);
40     if(strcmp(c,d)!=0)
41         printf("0");
42     else
43     {
44         p=gcd(m1/a,m2/b);
45         t=(int)sqrt(p+0.5);
46         for(i=1;i<=t;i++)
47             if(p%i==0)
48                 ans+=2;
49         if(t*t==p)    ans--;
50         printf("%d",ans);
51     }
52     return 0;
53 }