Codeforces Round #117 (Div. 2) D : Common Divisors
問題概要
長さL1,L2(<10^5)の文字列S1,S2が与えられるので、S1=x^n, S2=x^mとなっているようなxがいくつあるか求める問題。
解法
公約数全部試すのは高度合成数のときに危ないし、有名問題っぽい割に知らなかったので敬遠してたけど、大量に通されていたので愚直にやって間に合うと判断して愚直に書いた。ただ危ない感はあったので気持ち程度の枝刈りを入れた。
あるnに対して文字列S=x^nとなっているかどうかはKMPだのZ関数だの使わなくても|S|/nおきに一致しているか見ればO(|S|)で判定できる。
acceptされたコード
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX_L = (int)(1e5); int L[2]; char buf[2][MAX_L + 1]; bool ok[MAX_L + 1]; void init(){ for(int i=0; i<2; ++i){ scanf("%[^\n]%*c", buf[i]); L[i] = strlen(buf[i]); } } bool check(char str[], int L, int x){ int T = L / x; for(int i=0; i<x; ++i){ for(int j=0; j<T; ++j){ if(str[i] != str[i+j*x]){ return false; } } } return true; } int solve(){ int ans = 0; int d = __gcd(L[0], L[1]); for(int i=1; i<=d; ++i)if(!ok[i] && d%i == 0){ bool same = true; for(int k=0; k<i; ++k){ same &= (buf[1][k] == buf[0][k]); } if(same && check(buf[0], L[0], i) && check(buf[1], L[1], i)){ for(int j=i; j<=d; j += i)if(d%j == 0 && !ok[j]){ ok[j] = true; ++ans; } } } return ans; } int main(){ init(); printf("%d\n", solve()); return 0; }