SDUT 1465 公共因子

公共因子

Time Limit: 1000MS Memory limit: 65536K

题目描述#include <stdio.h>#include <string.h>#include <math.h>int a[1000000],b[1000000];char s1[1000000],s2[1000000],s3[1000000];int main(){ int i,j,n,m,s,t,l1,l2,top,top1,x; while(scanf("%s %s",s1,s2)!=EOF) { l1=strlen(s1); s=0; for(i=1,top=0;i<=l1;i++) { if(l1%i==0) { a[top++]=i; } } for(i=0,top1=0;i<=top-1;i++) { for(j=0;j<=a[i]-1;j++) { s3[j]=s1[j]; } if(a[i]==l1) { b[top1++]=a[i]; continue; } for(j=a[i];j<=l1-1;j+=a[i]) { for(x=0;x<=a[i]-1;x++) { if(s3[x]!=s1[j+x]) { break; } } if(x!=a[i]) { break; } } if(j==l1) { b[top1++]=a[i]; } } l2=strlen(s2); for(i=0;i<=top1-1;i++) { if(l2%b[i]==0) { for(j=0;j<=l2-1;j+=b[i]) { for(x=0;x<=b[i]-1;x++) { if(s1[x]!=s2[j+x]) { break; } } if(x!=b[i]) { break; } } if(j==l2) { s++; } } } printf("%d\n",s); } return 0;}