PKU 2406 Power Strings

• 最初に考えたときはナイーブな方法だと計算量が足りないなぁと延々と考えていた
• 繰り返される文字数kを全部回すとで通らない
• Nの約数の個数は個なので、Nの約数kだけ見ればとなり通る

static char input[2 * 1024 * 1024];

int main() {
	while (scanf("%s", input), strcmp(input, ".") != 0) {
		const int n = strlen(input);
		int answer = -1;
		for (int length = 1; length <= n; ++length) {
			if (n % length != 0) {
				continue;
			}

			bool ok = true;
			for (int i = length; ok && i < n; ++i) {
				ok = (input[i % length] == input[i]);
			}

			if (ok) {
				answer = n / length;
				break;
			}
		}

		printf("%d\n", answer);
	}
}