/*==============================================================================
  Лабораторна робота №4. Завдання 2. Варіант 19.
  Тема: цикли з розгалуженням, комбінаторні задачі.

  Умова (таблиця 4.3, варіант 19): натуральне число із n цифр є числом
  Армстронга, якщо сума його цифр, піднесених до n-го степеня, дорівнює
  самому числу (наприклад, 153 = 1^3 + 5^3 + 3^3 = 1 + 125 + 27).
  Визначити всі числа Армстронга, що складаються з двох, трьох та
  чотирьох цифр.

  Степінь обчислюється за рекурентним співвідношенням (послідовним
  множенням у цілій арифметиці), без бібліотечної функції pow().

  Виконав: Одарчук Олексій, КНУ імені Тараса Шевченка, ФІТ, група ІПЗ-11.

  Компілятор: gcc -std=c17
==============================================================================*/

#include <stdio.h>
#include <stdbool.h>

/*------------------------------------------------------------------------------
  intPower — піднести ціле число до натурального степеня.

  Реалізує рекурентне співвідношення  p(0) = 1,  p(i) = p(i-1) * base,
  тобто степінь накопичується послідовним множенням. Бібліотечна функція
  pow() не використовується: вона працює з дійсними числами і для цілих
  показників може давати результат виду 124.9999999, який після
  перетворення до цілого типу (відкидання дробової частини) дав би 124
  замість 125 і спотворив би порівняння.

  Параметри:
      base [вхідний] — основа степеня (цифра числа, 0..9);
      exp  [вхідний] — показник степеня (кількість цифр числа, 2..4).

  Повертає: значення base у степені exp.

  Локальні змінні:
      result — накопичуване значення степеня.
------------------------------------------------------------------------------*/
long long intPower(int base, int exp)
{
    long long result = 1;

    for (int i = 0; i < exp; ++i)
        result *= base;

    return result;
}

/*------------------------------------------------------------------------------
  digitCount — кількість цифр у десятковому записі числа.

  Параметри: n [вхідний] — натуральне число.
  Повертає : кількість цифр (для n = 0 повертає 1).

  Локальні змінні:
      count — лічильник цифр;
      rest  — залишок числа, що ще не оброблено.
------------------------------------------------------------------------------*/
int digitCount(long long n)
{
    int count = 0;
    long long rest = n;

    do {
        ++count;
        rest /= 10;
    } while (rest > 0);

    return count;
}

/*------------------------------------------------------------------------------
  isArmstrong — чи є число числом Армстронга.

  Параметри:
      n       [вхідний]  — число, що перевіряється;
      sumOut  [вихідний] — адреса змінної для суми степенів цифр;
                           може бути NULL.

  Повертає: true — сума цифр, піднесених до степеня, що дорівнює кількості
            цифр числа, збігається із самим числом.

  Локальні змінні:
      digits — кількість цифр числа;
      sum    — накопичувана сума степенів цифр;
      rest   — залишок числа, що ще не оброблено;
      digit  — чергова цифра числа.
------------------------------------------------------------------------------*/
bool isArmstrong(long long n, long long *sumOut)
{
    const int digits = digitCount(n);

    long long sum = 0;
    long long rest = n;

    while (rest > 0) {
        const int digit = (int)(rest % 10);
        sum += intPower(digit, digits);
        rest /= 10;
    }

    if (sumOut != NULL)
        *sumOut = sum;

    return sum == n;
}

/*------------------------------------------------------------------------------
  printExpansion — вивести розклад числа Армстронга у вигляді суми степенів
                   окремим рядком з відступом.
                   Наприклад: 153 = 1^3 + 5^3 + 3^3 = 1 + 125 + 27

  Параметри: n [вхідний] — число Армстронга.

  Локальні змінні:
      digits    — кількість цифр числа;
      divisor   — дільник для виділення старшої цифри;
      rest      — залишок числа, що ще не оброблено;
      digit     — чергова цифра;
      i         — номер позиції цифри.
------------------------------------------------------------------------------*/
void printExpansion(long long n)
{
    const int digits = digitCount(n);

    /* Найстарший розряд: 10^(digits-1), обчислюється множенням. */
    long long divisor = 1;
    for (int i = 1; i < digits; ++i)
        divisor *= 10;

    printf("  %lld = ", n);

    long long rest = n;
    for (int i = 0; i < digits; ++i) {
        const int digit = (int)(rest / divisor);
        printf("%d^%d", digit, digits);
        if (i < digits - 1)
            printf(" + ");
        rest %= divisor;
        divisor /= 10;
    }

    printf(" = ");

    divisor = 1;
    for (int i = 1; i < digits; ++i)
        divisor *= 10;

    rest = n;
    for (int i = 0; i < digits; ++i) {
        const int digit = (int)(rest / divisor);
        printf("%lld", intPower(digit, digits));
        if (i < digits - 1)
            printf(" + ");
        rest %= divisor;
        divisor /= 10;
    }

    printf("\n");
}

/*------------------------------------------------------------------------------
  scanRange — перебрати всі числа заданої розрядності та вивести знайдені
              числа Армстронга.

  Параметри: digits [вхідний] — кількість цифр (2, 3 або 4).
  Повертає : кількість знайдених чисел Армстронга.

  Локальні змінні:
      low, high — межі діапазону чисел заданої розрядності;
      found     — лічильник знайдених чисел;
      checked   — лічильник перевірених чисел.
------------------------------------------------------------------------------*/
int scanRange(int digits)
{
    long long low = 1;
    for (int i = 1; i < digits; ++i)
        low *= 10; /* 10, 100, 1000 */

    const long long high = low * 10 - 1; /* 99, 999, 9999 */

    printf("\n=== Числа Армстронга з %d цифр (діапазон %lld..%lld) ===\n", digits, low,
           high);

    int found = 0;
    long long checked = 0;

    for (long long n = low; n <= high; ++n) {
        ++checked;
        if (isArmstrong(n, NULL)) {
            printExpansion(n);
            ++found;
        }
    }

    if (found == 0)
        printf("  чисел Армстронга цієї розрядності не існує\n");

    printf("  Перевірено чисел: %lld, знайдено: %d\n", checked, found);
    return found;
}

/*------------------------------------------------------------------------------
  Головна функція. Послідовно перебирає двоцифрові, трицифрові та
  чотирицифрові числа й виводить знайдені числа Армстронга.

  Локальні змінні:
      total  — загальна кількість знайдених чисел;
      digits — поточна розрядність.
------------------------------------------------------------------------------*/
int main()
{
    printf("Лабораторна робота №4, завдання 2 (варіант 19)\n");
    printf("Виконав: студент групи ІПЗ-11 Одарчук Олексій\n");
    printf("Пошук чисел Армстронга з двох, трьох та чотирьох цифр\n");
    printf("Число з n цифр є числом Армстронга, якщо сума його цифр,\n"
           "піднесених до n-го степеня, дорівнює самому числу.\n");

    int total = 0;
    for (int digits = 2; digits <= 4; ++digits)
        total += scanRange(digits);

    printf("\n============================================================\n");
    printf("Усього знайдено чисел Армстронга: %d\n", total);

    return 0;
}