1) Поскольку в задаче нет ограничения на память - то мы можем спокойно использовать мемоизацию для хранения нужных нам ответов.
2) В процессе ввода (предполагается что ввод будет неспешный и задумчивый) чисел {n} мы строим хеш-таблицу всех возможных сочетаний пар {m(i),m(j)} где ключами будет кратность суммы этой пары. Здесь ключом будет сет чисел которые кратны этой сумме. Для простоты - табличку можно денормализовать и хранить несколько записей на 1 ключ. Например для {20,4}, будет кратность 2, 3, 4, 6, 8.
3) Еще для упрощения можно отбросить составные числа ключа (4, 6, 8) и хранить цепочку простых.
4) У этой задачи - бесконечное направление оптимизаций системы хранения этой таблицы. Зависит от дерзости автора. А он ... как видно парень очень суровый и дерзкий.