Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:soIn Reply To:so Posted by:tayu at 2005-10-10 14:53:48 #include<iostream> #include<cstring> using namespace std; char mat[10001][100]; int next[10005]; int r,c; inline char getc(int p,bool dec,int k){ if(dec) return mat[k][p]; else return mat[p][k]; } int getpows(int p,bool dec){//1 c 0 r int n; if(dec)n=r; else n=c; next[0]=-1;int i,j; for(i=1,j=-1;i<n;i++) { while(j>-1&&getc(p,dec,j+1)!=getc(p,dec,i))j=next[j]; if(getc(p,dec,j+1)==getc(p,dec,i))j++; next[i]=j; } return n-1-next[n-1]; } int gcd(int a,int b){ return b?gcd(b,a%b):a; } int lcm(int a,int b){ return a/gcd(a,b)*b; } int main(){ // freopen("0.txt","r",stdin); // freopen("1.txt","w",stdout); scanf("%d%d",&r,&c); int i,j; for(i=0;i<r;i++) for(j=0;j<c;j++) scanf(" %c",&mat[i][j]); int res=1; int ans=1; for(i=0;i<r;i++) ans=min(c,lcm(ans,getpows(i,0))); res*=ans;ans=1; for(i=0;i<c;i++) ans=min(r,lcm(ans,getpows(i,1))); res*=ans; printf("%d\n",res); } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator