найти любой набор целых чисел a1, a2, …, ak (1 ≤ ai < n) такой, что выполняется равенство

Question

Вам дано число n. Необходимо найти любой набор целых чисел a1, a2, …, ak (1 ≤ ai < n) такой, что выполняется равенство:

Если такого набора не существует, то нужно вывести -1.

Если существует набор целых чисел a1, …, ak, удовлетворяющий условиям, то выведите его в сжатом формате, а именно

в первой строке выведите количество различных чисел m (1 ≤ m ≤ 10^5) в наборе. Можно показать, что если ответ существует, то различных чисел в нём не больше 10^5.
В следующих m строках выведите пару чисел xi pi (1 ≤ xi < n, 1 ≤ pi ≤ n) — элемент из последовательности и количество его вхождений соответственно. Если подходящего набора не существует, то в единственной строке выведите -1.

Пример теста:

Ввод    Вывод
24
        3
        2 1
        12 1
        1 10


19     -1

Answer 1

Если число делится на какие-то два множителя, большие 1 - все, сумму добиваем единицами...

n = int(input())

i = 2
count = 0
m = [0,0,0]
c = [0,0,0]
while i*i <= n:
    if n%i == 0:
        if i*i == n:
            m[count] = i
            c[count] = 2
            count += 1
        else:
            m[count] = i
            c[count] = 1
            count += 1
            m[count] = n//i
            c[count] = 1
            count += 1
        if n//i+i != n:
            m[count] = 1
            c[count] = n - n//i - i
            count += 1
        break
    else:
        i += 1

if i*i > n: print(-1)
else:
    print(count)
    for i in range(count):
        print(m[i],c[i])

БЛОГ НА HUSL

найти любой набор целых чисел a1, a2, …, ak (1 ≤ ai < n) такой, что выполняется равенство

Ответы (1 шт):