7719. Суммы

Представить целое число n в виде суммы как минимум двух последовательных натуральных чисел. Например:

• 10 = 1 + 2 + 3 + 4

• 24 = 7 + 8 + 9

Если существует несколько решений, то следует вывести то, которое содержит меньшее количество слагаемых.

Вход. Первая строка содержит количество тестов t. Каждый тест состоит из одной строки и содержит одно целое число n (1 ≤ n ≤ 10⁹).

Выход. Для каждого теста вывести в отдельной строке равенство в формате:

n = a + (a + 1) + ... + b

Если решения не существует, то вывести одно слово IMPOSSIBLE.

Пример входа	Пример выхода
3 8 10 24	IMPOSSIBLE 10 = 1 + 2 + 3 + 4 24 = 7 + 8 + 9

РЕШЕНИЕ

разложение на множители

Анализ алгоритма

Рассмотрим разложение числа n в виде d слагаемых:

n = a + (a + 1) + ... + (a + d – 1) =

Следует найти такие a и d ≥ 2 , что (2a + d – 1) d = 2n. Множители 2a + d – 1 и d имеют разную четность. Перебираем значение d от 2 до . Если 2n делится на d, то проверяем, является ли 2n / d + 1 – d четным. Если ответ утвердительный, то имеем решение (пару a и d) с наименьшим значением d.

Реализация алгоритма

Читаем входные данные.

scanf("%d",&tests);

while(tests--)

{

scanf("%d",&n); flag = 0;

Перебираем значение d от 2 до .

for(d = 2; d <= sqrt(2 * n); d++)

{

Если 2n делится на d, то проверяем является ли a = 2n / d + 1 – d четным.

if (2 * n % d == 0)

{

a = (2 * n) / d + 1 - d;

if (a % 2 == 0)

{

a /= 2;

В случае существования решения выводим ответ и устанавливаем flag = 1. При этом если имеется несколько решений, то первым будет найдено решение с наименьшим d (то есть с наименьшим количеством слагаемых).

printf("%d = %d",n,a);

for(i = 1; i < d; i++)

printf(" + %d",a + i);

printf("\n"); flag = 1;

break;

}

}

}

Если решение не найдено, то выводим IMPOSSIBLE.

if (flag == 0) printf("IMPOSSIBLE\n");

}

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int tests = con.nextInt();

while(tests-- > 0)

{

int n = con.nextInt();

int flag = 0;

for(int d = 2; d <= Math.sqrt(2 * n); d++)

{

if (2 * n % d == 0)

{

int a = (2 * n) / d + 1 - d;

if (a % 2 == 0)

{

a /= 2;

System.out.print(n + " = " + a);

for(int i = 1; i < d; i++)

System.out.print(" + " + (a + i));

System.out.println();

flag = 1;

break;

}

}

}

if (flag == 0) System.out.println("IMPOSSIBLE");

}

con.close();

}

}

Python реализация

import math

tests = int(input())

while tests > 0:

tests -= 1

n = int(input())

flag = 0

for d in range(2, int(math.sqrt(2 * n)) + 1):

if 2 * n % d == 0:

a = (2 * n) // d + 1 – d

if a % 2 == 0:

a //= 2

print(n, " = ", a, end ="")

for i in range(1, d):

print(" + ", a + i, end ="")

print()

flag = 1;

break

if flag == 0: print("IMPOSSIBLE");