2348번 - 내가 무릎을 꿇은 것은 추진력을 얻기 위함이었다

문제

다음 조건을 만족하는 길이가 $n$인 수열 $A=\{a_1,$ $\cdots ,$ $a_n\}$을 추진력이 $f_A$인 추진력 수열이라 하자.

• $n\ge 3$이다.
• 1ドル\le i\le n$인 모든 정수 $i$에 대하여 $a_i$는 정수이고 1ドル\le a_i\lt 10^9$이다.
• $a_{i+1}=a_i+d(1\le i\le n-2)$을 만족하는 양의 정수 $d$가 존재한다. 즉, $A$에서 마지막 항 $a_n$을 제거한 수열 $\{a_1,$ $\cdots ,$ $a_{n-1}\}$이 공차가 양의 정수인 등차수열이다.
• $a_{n}=a_{n-1} \cdot f_A$ 를 만족하는 2ドル$ 이상인 정수 $f_A$가 존재한다.

예를 들어, 수열 $A=\{2,$ 3,ドル$ 4,ドル$ 8ドル\}$은 $d=1,ドル $f_A=2$일 때 모든 조건을 만족하므로 추진력 수열이다.

추진력 수열 $\{2,$ 3,ドル$ 4,ドル$ 8ドル\}$으로 추진력을 얻는 모습

숫자로만 이루어진 문자열 $S$가 주어질 때, $S=(a_1,$ $\cdots ,$ $a_n$을 공백 없이 이어 붙인 문자열$)$을 만족하는 추진력 수열 $A=\{a_1,$ $\cdots ,$ $a_n\}$가 존재하는지 확인하는 프로그램을 작성해 보자.

단, $a_i$를 문자열로 바꿀 때는 앞에 불필요한 0을 붙일 수 없으며, $f_A$가 너무 크면 다리에 쥐가 나기 때문에 $f_A$를 최소화하는 $A$를 찾아야 한다.

입력

첫째 줄에 문자열 $S$가 주어진다. $S$의 길이는 3ドル$ 이상 2ドル,円 348$ 이하이고, $S$의 각 문자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중 하나이다.

단, 첫 번째 문자가 0인 문자열은 주어지지 않는다.

출력

$S$에 대해 문제의 조건에 맞는 추진력 수열 $A$가 존재한다면, $f_A$를 정수로 출력한다. $A$가 두 개 이상 존재하는 경우에는 가능한 $f_A$ 중 가장 작은 것을 출력한다.

만약 문제의 조건에 맞는 추진력 수열 $A$가 존재하지 않으면 0을 출력한다.

제한

힌트