Задача: Полярные единички с большими числами

Question

Вроде бы задачка сверх простая, но в условии число в диапазоне от 1 до 10^6.

#include <iostream>
using namespace std;

int main()
{
    setlocale(LC_ALL, "Russian");

    unsigned long long int inputNumber;

    cout << " Введите число: ";
    cin >> inputNumber;

    cout << " Вывод: ";
    for (unsigned long long int i = 1; i <= 1111111111111111111; i = i * 10 + 1)
    {
        if (i % inputNumber == 0)
        {
            cout << i << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
}

Значит нужно какой-то тип данных на подобии BigInteger, но где его взять, что-бы работал быстро и корректно. Или можно обойтись без сторонних библиотек?

Задача: Программист на Северном полюсе работал за компьютером в варежках и поэтому мог набирать только 0 и 1, а клавиша 0 запала. Сможет ли он набрать число, состоящее только из единиц и при этом кратное заданному N?

Входные данные Программе дано число N (1 ≤ N ≤ 106). Вывести минимальное число, удовлетворяющее требованию, или "NO" , если такого числа не существует.

Answer 1

Просто смотрим остатки при добавлении единички... Никакой длинной арифметики.

#include <iostream>
#include <iomanip>

using namespace std;


int main(int argc, const char * argv[])
{
    int N;
    cin >> N;
    for(int r = 0, n = 0; n <= N; ++n)
    {
        r = (r*10+1)%N;
        if (r == 0)
        {
            for(int i = 0; i <= n; ++i) cout << 1;
            cout << endl;
            return 0;
        }
    }
    cout << "NO\n";
}

Answer 2

По копросу оптимизации.
Можно рассмотреть, какую последнюю цифру не может иметь число, чьтоб кратное еиму оканчивалось единицей. Например, на что ни множь 6 - а 1 не получишь. Так что решение Harry с оптимизацией выглядит так:

int main() {
    int N;
    cin >> N;

    switch (N % 10) {
        case 1:
        case 3:
        case 7:
        case 9:
            for (int r = 0, n = 0; n <= N; ++n) {
                r = (r * 10 + 1) % N;

                if (r == 0) {
                    for (int i = 0; i <= n; ++i) cout << 1;

                    cout << endl;
                    return 0;
                    }
                }
        }

    cout << "NO\n";
    }

БЛОГ НА HUSL

Задача: Полярные единички с большими числами

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