Здравствуйте, xma, Вы писали:
xma>шо за пургу ты несёшь ? как ты одномерный массив состоящий из пар (10, 2), (1, 5) сделаешь одномерно возрастающим ? (так чтобы пары сохранились в последовательности)
Тут нет никаких пар. Есть множество чисел. Попарно различных — это означает, что каждое число встречается в нём не более 1 раза.

xma>натуральные или целые ? обычные int 4 байта ?
Натуральные.

S>>В пределах миллисекунды
xma>взаимоисключающие требования на чём миллисекунда то, на CPU (однопоток/многопоток?) или GPGPU ?
На обычном CPU, предпочтительно в однопотоке. Задача — гражданская, мы не будем выдвигать никаких требований к аппаратуре.
xma>ну и приблизительно сколько чисел — тысячи / миллионы или миллиарды ? (в последнем случае на миллисекунду думаю что рассчитывать маловероятно)
Пусть будут десятки чисел.
xma>можно предположить что (если задача имеет быстрое решение, то) тут фишка где то в диофантовых уравнениях — и если нужно очень быстро и точно, то копать куда то туда (я их лично не проходил, в школьной программе их тогда вроде отменили)
Да явно имеет. Интуитивно кажется, что для взаимно простых n и m любое число больше (n-1)*(m-1) представимо в виде их линейной комбинации; это означает, что "перебирать" придётся относительно небольшое количество чисел.