The first thing we should do is remove duplicates of $a_i$. After this, we'll assume all the $a_i$ are distinct, and let $N'$ denote the number of distinct $a_i$. Note that if $N' \leq 3$, then any $L$ satisfies the second condition. So, the answer is just $1 + 2 + \cdots + (\min a_i)/4$.
Subtask 1 ($a_i\leq 10^6$):
For this subtask, we first consider the following naive algorithm: Let $U = (\min a_i)/4$ be an upper bound on $L$. For each $1\leq L \leq U$, we can check how many possible values of $a_i\pmod L$ there are. It turns out that if we break once we see 4 distinct values, then we will pass this subtask.
Here is an implementation:
N = input() S = list(set([int(x) for x in input().split()])) U = min(S) // 4 if len(S) < 4: print(U*(U+1)//2) exit() def test(L): mods = set() for a in S: mods.add(a%L) if len(mods) >= 4: return False return True print(sum([L for L in range(1, U+1) if test(L)]))
Now, why do we pass? A naive analysis says that this time should take $O(UN')$ time, where $U\leq 2.5\cdot 10^5$ and $N' \leq 10^4$. So this should not actually be fast enough.
Let's consider the test function again, which takes $O(N')$ time in the worst case. However, note that in order for the function to not return after 4 iterations (and so only take $O(1)$ time), among $a_1\bmod L, a_2\bmod L, a_3\bmod L, a_4\bmod L$, there are at most $3$ distinct values.
This implies that $L$ divides one of $(a_2 - a_1, a_3 - a_1, a_4 - a_1, a_3 - a_2, a_4 - a_2, a_4 - a_3)$. Now, if we let $n(A)$ denote the maximum number of divisors that a number at most $A$ can have, then we see that for all but at most $6n(10^6)$ values of $L$, we break after 4 loop iterations. So, we can bound the runtime of this step by $O(U + n(10^6)\cdot N')$, where we run the loop $O(U)$ times, and only run past 4 iterations $O(n(10^6))$ times. Since $n(10^6) \leq 2\cdot 10^3$ (here, note that any positive integer $x$ has at most $2\sqrt x$ divisors), this will run in time.
General Case ($a_i \leq 4\cdot 10^9$):
Now, $U$ can be up to $10^9$, so the preceding algorithm is too slow. On the other hand, $n(4\cdot 10^9)$ is actually $2000$, so we just need to speed up the $O(U)$ step. To do this, instead of checking every possible value of $L$ and seeing if it breaks after trying the first four $a_i$, we will instead explicitly only consider $L$ that would not have broken. The only such values of $L$ are those that divide one of $(a_2 - a_1, a_3 - a_1, a_4 - a_1, a_3 - a_2, a_4 - a_2, a_4 - a_3)$. So, we can just compute these divisors. We can compute the divisors of $A$ in $O(\sqrt A)$ time, so the total runtime of this is $O(\sqrt{\max a_i} + n(4\cdot 10^9) \cdot N')$, which runs in time.
Here is an implementation:
N = input() S = list(set([int(x) for x in input().split()])) U = min(S) // 4 if len(S) < 4: print(U*(U+1)//2) exit() divs = set() for i, s in enumerate(S[:4]): for _, r in enumerate(S[i:4]): diff = abs(s-r) for t in range(1, int(diff**(0.5) + 1)): if diff%t == 0: divs.add(t) divs.add(diff//t) def test(L): if L > U: return False mods = set() for a in S: mods.add(a%L) if len(mods) >= 4: return False return True print(sum([L for L in divs if test(L)]))
Danny Mittal's implementation:
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashSet; import java.util.Set; import java.util.StringTokenizer; public class Cowlendar { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine()); Set<Long> months = new HashSet<>(); StringTokenizer tokenizer = new StringTokenizer(in.readLine()); long maxWeekLength = Integer.MAX_VALUE; for (; n > 0; n--) { long month = Long.parseLong(tokenizer.nextToken()); months.add(month); maxWeekLength = Math.min(maxWeekLength, month / 4L); } if (months.size() <= 3) { System.out.println((maxWeekLength * (maxWeekLength + 1L)) / 2L); } else { Set<Long> candidates = new HashSet<>(); Long[] distinctMonths = months.toArray(new Long[0]); for (int j = 0; j < 4; j++) { for (int k = 0; k < j; k++) { long diff = Math.abs(distinctMonths[k] - distinctMonths[j]); for (long x = 1; x <= 100000; x++) { if (diff % x == 0L) { candidates.add(x); candidates.add(diff / x); } } } } long answer = 0; for (long candidate : candidates) { if (candidate <= maxWeekLength) { Set<Long> seen = new HashSet<>(); for (long month : distinctMonths) { seen.add(month % candidate); } if (seen.size() <= 3) { answer += candidate; } } } System.out.println(answer); } } }