Практика: Пары и Тройки

Девять задач, в которых считаются пары или тройки. Сначала решите, какие пары считаются — условие всегда это говорит, — потом напишите циклы, а потом проверьте, сколько шагов они делают при самом большом вводе.

• Пары с равными значениями и Пары с целевой суммой — это пары позиций i < j в векторе: внутренний цикл начинается с i + 1. При n ≤ 5000 это около 1,25 · 10⁷ проверок — нормально.
• В Парах с целевой суммой K и a[i] + a[j] доходят до 2 · 10⁹: читайте K и сравнивайте сумму как long long. int не вмещает 2 · 10⁹.
• Пары с заданной суммой — то же самое, только по числам от 1 до N вместо вектора.
• Пары делителей и Произведения, кратные K считают упорядоченные пары: (1, 2) и (2, 1) — разные, и i = j тоже считается, поэтому оба цикла идут от 1 до N. В Парах делителей для надёжности храните количество в long long, а произведение i * j вычисляйте до % K — оно до 9 · 10⁶ и помещается в int.
• Пары с заданным произведением: i ≤ j, поэтому j начинается с i.
• Проверка на сумму двух квадратов и Сумма двух квадратов берут положительные a и b. Впишите ограничение в проверки циклов, как в уроке (a * a < N, a * a + b * b <= N): два цикла до самого N = 10⁶ — это 10¹² шагов. В Сумме двух квадратов условие a ≤ b считает каждую пару один раз.
• Пифагоровы тройки: 1 ≤ a ≤ b ≤ c ≤ N, три цикла, каждый начинается с переменной предыдущего. При N = 500 c * c не больше 250 000 — переполнения нет.