**Author:** Vaibhav Tulsyan

**Tester:** Istvan Nagy

**Editorialist:** Misha Chorniy

# Difficulty:

Medium

# Pre-Requisites:

greatest common divisor (gcd)

# Problem Statement

You are given a string $S$ which consists digits as characters. Let's iterate over all partitions into $K$ parts, where $K$ in the range between $X+1$ and $Y+1$ and each part must has a length between $1$ and $M$. After that, let's transform each part in integer and calculate $gcd$ of received integers. Find the maximal value of $gcd$ over all such partitions.# Explanation

# Subtask 1

For the first subtask, we can iterate over all partitions using bitmasks. After each of the first $N-1$ digits we can put separator or don't put, hence it takes $2^{N-1})$ operations in the worst case. After that go through the partition in $O(N)$ and calculate $gcd$ manually. This approach takes time $O(2^N*(N+log(10^M))$, not $O(2^N*N*log(10^M))$. If you have array and you need to find $gcd$ of it's elements, next algorithm will work in $O(N + log (max A))$, not in $O(N log (maxA))$. You can prove it.

```
g = 0
for i = 1..N
g = gcd(g, A*)
```

# Subtask 2

For the second subtask we need something smarter than bitmasks. Let's put the first separator, we will get some number $g$, which values of $gcd$ is possible after fixing the first integer. If we process $gcd(g, x)$ we'll obtain some divisor of the number $g$.

How many first integers can be? At most $M$. How many distinct values of $gcd$ can be? At most $M * O(f(10^M))$. f(X) - is the maximal number of divisors of an integer less than $X$. $f(N)$ can be approximately estimated in $N^{1/3}$, for numbers less than $10^{18}$. Therefore, can be $O(M * 10^{10/3})$ distinct values of $gcd$, practically is much less. It gives us the next idea for solution:

Let $DP_{i, j}$ - set of the possible values of $gcd$ on prefix $S[1..i]$, if we put exactly $j$ separators and the last one placed exactly after position $i$.

What is the start values for this $DP$?$DP_{i, 1}$ = {integerValue($S[1..i]$)}, when $1 <= i <= min(N, M)$

How to recalculate $DP$, which transitions exist?When we know set of the values of $gcd$ for state $DP_{i,j}$, we can iterate over next separator after position $i$:

$DP_{i,j}$ -> $DP_{ni,j+1}$, where $i < ni <= min(N, i + M)$, and new value of the $gcd$ will be $gcd(g, integerValue(S[i+1..ni]))$

What will be the answer? It will be the maximal value of $gcd$ over all values $DP_{N,i}$, where $X + 1 <= i <= Y + 1$, because we split array in exactly $i$ parts. Let's write pseudocode of such solution:

```
for i = 1..min(N,M)
DP*[1].insert(integerValue(S[1..i])) //initialize DP
for i = 1..N
for sep = 1..Y
for ni = i+1..min(N,i+M):
tempValue = integerValue(S[i+1..ni]))
//It's better to precalculate all values S[i..j]
for g inside DP*[sep]
DP[ni][sep + 1].insert(gcd(tempValue, g))
ans = 1
for sep = X+1..Y+1
for g in DP*[sep]
ans = max(ans, g)
```

How to estimate time of work? Each prefix in the string may have $O(M * 10^{10/3})$ values of $gcd$ in the worst case. From each value can be $O(M)$ transitions. Hence total complexity can be estimated in $O(N * M^2 * 10^{10/3})$, but practically is much less.

# Solution:

Setter's solution can be found here

Tester's solution can be found here

**Please feel free to post comments if anything is not clear to you.**