Указать наименьшее значение, которое делится на число составленное из последовательности цифр

@NuMeRiC_ · Регистрация: 03.06.2019

Студворк — интернет-сервис помощи студентам

Условие:
Последовательные натуральные числа от a до b выписали одно за другим без пропусков, при этом образовалось число, нацело делится на натуральное c. По данным a и c указать наименьшее значение b.

Входные данные:
Два числа a и c (a, c <10000, a ≤ b).

Исходные данные:
Вывести число b.

Пример:
входные данные:
11 3

Исходные данные:
13
//объяснение: имеем а = 11. Оно не кратное 3, тогда добавляем к числу сзади 2 цифры числа 12, число уже = 1112. Оно все еще не кратное 3, тогда плюсуем 13: число = 111213, и оно уже кратное 3. Переменная b в таком случае будет равна 13 - последнему прибавленному натуральному числу.

У меня получился код, на подобии этого:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <math.h>
using namespace std;
//Функция leng узнает длину числа
int leng(int a) {
    int k = 1;
    while (a > 9) {
        a = a / 10;
        k++;
    }
    return k;
}
 
 
//В главной функции реализуется ввод а и с. 
int main()
{
    int a, b, c; cin >> a >> c; 
    if (a % c == 0) { b = a; }//Если число а делится без останка на заданное с, то b = a.
    else {
        int ch = a; int k = 0; //Иначе добавляем цикл
        while (ch % c != 0) {
            ch = ch * pow(10, leng(a)) + a + 1; //Где ch - число, состоящее из натуральных от а до b
            a++; k++;
            if (a + 1 == 9) { k++; } //Если последнее число равно 9, добавляем к длине последнего 1.
        }
        b = ch % int(pow(10, k));
    }
    cout << b; //Выводим натуральную переменную b на экран.
}

Смысл в том, что на eolymp задача не проходит, и повремени, и по ответам. Прошу помочь.

Байт · 03.06.2019, 22:14

NuMeRiC_, самая главная беда здесь в том, что образованное приписками число может оказаться довольно большим. и обычная арифметика с ним не справится.
Хотя тут можно попытаться выкрутится, так как деление нам требуется по модулю c < 10000

Добавлено через 10 минут
И, конечно, pow надо засунуть куда подальше подальше. Задача целочисленная, и нечего привлекать неточные функции работы с плавающими числами.
Но, наверное, может помочь такое соображение
(x*y +z) % c математически равно (((x%c)*(y%c))%c + z%c)%c - гомоморфизм кольца целых чисел на кольцо вычетов по модулю.
И вот это соображение позволит обойтись без длинной арифметики.
Как-бы алгоритм просматривается, но глаза слипаются...

IGPIGP · 03.06.2019, 22:27

Сообщение от NuMeRiC_

Задачка для "новичков"

Я тута. Не уверен что это быстро и правильно, но чего-то оно считает...

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;
 
int main(int argc, char* argv[])
{
int a, b, c, d, e;
//cin>>a>>b; //для произвольных чисел
a=11, c=3, b;//для теста
b=d=a;
 
    do
    {
        e=++b;
        while(e/=10)
        d *= 10;
        d *= 10;
        d += b;         
    }
    while(d%c);
cout<<d<<endl;
cout<<b<<endl;
cin.get();
return 0;
}
}

Байт · 04.06.2019, 09:32

Сообщение от IGPIGP

чего-то оно считает...

Вы убрали нелепый pow, что уже шаг вперед. Но код ваш работать не должен. Для больших c все быстро рухнет. И даже не очень больших.
Представьте, a = 1, c=100 даст b = 100. А полученное число d будет иметь 192 цифры.

Добавлено через 11 минут

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int tenP(int a)  // Степень десятки
{
  int p = 1;
  while(a) {
    p*10;
    a/=10;
  }
   return p;
}
int main()
{
   ......
  b = a; 
  int x = a%c;
  while( x% c) {
     b++;
     x = (((tenP(b)%c)*(x%c))%c + b%c)%c 
  }
   cout << b;
}

Не проверял. Тому кто возьмет на себя этот необходимый, но скушный труд - мое почтение и благодарность.

IGPIGP · 04.06.2019, 09:52

Сообщение от Байт

А полученное число d будет иметь 192 цифры.

Согласен, код предполагает что данных вызывающих переполнение не будет. Более того, выбран тип int и он знаковый в двух смыслах, так как выбран таковым намеренно. Ведь новичковская же задача. И да. Лучше unsigned long long выбрать. Но если решать в общем виде, анализируя сумму без её вычисления, нужно уже теоремки подоказывать. Тут есть о чём подумать... И я подумаю, но боюсь, тут есть люди которые гораздо сильнее меня и на этом поприще. Вы в частности.

Добавлено через 16 минут

Сообщение от Байт

C++
1
x = (((tenP(b)%c)*(x%c))%c + b%c)%c

Проверить делимость суммы остатков? Это уже с учётом их порядков? Может быть... Идея во всяком разе хорошая. Это конечно раздвинет возможности алгоритма. И даже может сделать его быстрее. Позже подойду.

Байт · 04.06.2019, 10:19

ДорогойIGPIGP!

Сообщение от IGPIGP

код предполагает что данных вызывающих переполнение не будет.

Так в этом-то и вся фишка задачи!

Сообщение от IGPIGP

Лучше unsigned long long

Не нужно. с < 10000. И даже квадраты за 32-битовый int не вылезают.

Сообщение от IGPIGP

нужно уже теоремки подоказывать.

Математика там очень простая. Доступная любознательному семикласснику. Я там использовал заумное слово "гомоморфизм", но сводится оно к тому, что для того, определить остаток деления суммы x = 123456789 y = 2134657 на 37, вовсе не обязательно складывать x + y а потом делить. Можно получить остатки x%37 y%37 и сложить уже их.
А если "по-умному"
f(x+y) = f(x) + f(y)
f(x*y) = f(x)*f(y)
Это и есть "гомоморфизм" (Умеют же математики словечки придумывать!

)

Добавлено через 12 минут
А вот чтобы доказать, что алгоритм кончится, тут, да - подумать надо.... Я вот не вижу простого доказательства.... Может быть к математикам обратиться...

Добавлено через 5 минут
Можно ли гарантировать делимость полученного числа?

IGPIGP · 04.06.2019, 12:08

Сообщение от Байт

А вот чтобы доказать, что алгоритм кончится, тут, да - подумать надо.... Я вот не вижу простого доказательства.... Может быть к математикам обратиться...

Думаю, всё дело в том, что остаток остатка от остатка .... (до бесконечности) равны остатку. То есть, одного шага должно хватить. Или нет?

Сообщение от Байт

Может быть к математикам обратиться...

Сообщение от Квай Гон

Может обратится к Хаттам? Они нас рассудят.

Те ещё бандиты.

Байт · 04.06.2019, 23:11

Сообщение от IGPIGP

одного шага должно хватить. Или нет?

Нет. Бандиты-математики показали случай, когда не хватило и миллиона шагов. Однако, ни доказать, ни опровергнуть пока не смогли. Ибо что такое миллион для бесконечности? Тоненькая, исчезающая тоненькая пленочка над толщей океана! Правда, эхолот мысли иногда позволяет узнать некоторые закономерности в тайнах глубин...

IGPIGP · 05.06.2019, 00:09

Байт, я может всё понял по своему, но мне кажется, что для операции остаток (%) :
f(a+b)=f(f(a)+f(b))
а не просто:
f(a+b)=f(a)+f(b)
А для произведений совсем не получается (у меня). Вот пара чисел 10 и 21
10%21=10
100%21=16
1000%21=13
10000%21=4
а ведь произведение остатков для 100 должно было дать 100?
Для степеней чисел, а нас интересует, как я понимаю, степень 10-ки которая и придаёт итоговому числу его протяженность многоразрядную и ко всякому переполнению приводящую, получается вроде:
f(a*a*a*a)=f(a*a*a*f(a))
но это не только для 4-й степени, а можно смело многоточия расставить как-то так:
f(a*a*...*a*a)=f(a*a*...*a*f(a))

C++
1
2
3
4
5
6
7
8
9
    cout<<"(10)%21 "<<(10)%21<<endl;
    cout<<"(10*10)%21 "<<(10*10)%21<<endl;
    cout<<"(10*10*10)%21 "<<(10*10*10)%21<<endl;
    cout<<"(10*10*10*10)%21 "<<(10*10*10*10)%21<<endl;
 
    cout<<"(10)%21 "<<(10)%21<<endl;
    cout<<"(10*10)%21 "<<(10*(10)%21)%21<<endl;
    cout<<"(10*10*10)%21 "<<(10*10*(10)%21)%21<<endl;
    cout<<"(10*10*10*10)%21 "<<(10*10*10*(10)%21)%21<<endl;

Добавлено через 12 минут
А если учесть что:
f(a*b)=f(a*f(b))
то применяя это рекурсивно к степеням получаются трудно записываемые выражения (скобок много). И алгоритм напрашивается рекурсивный. Тут Ivana бы помог. (имхо)

Байт · 05.06.2019, 00:16

Сообщение от IGPIGP

мне кажется, что для операции остаток (%) :
f(a+b)=f(f(a)+f(b))

Да. Все правильно. Вам кажется почти правильно.
Но там есть некоторые маленькие хитрости. В арифметике "по модулю" считается, что числа, отличающиеся на этот модуль просто равны.
16 = 37 = -5 (mod 21)
10*10 = 100 = 16 (mod 21)
16*10 = 160 = 13 = -8 (mod 21)
Строго математически это выглядит так. Множество чисел разбивается на "классы" (никакого отношения не имеющие к классам С++)
К одному классу принадлежат числа, дающие одинаковый остаток на этот "модуль" (опять же, не путать с модулем, как абсолютной величиной, с функциями abs, fabs)
2, 23, 44, -19... - это все числа одного класса для модуля 21
Но чтобы не иметь дела с классами (множествами), ибо это утомительно писать "2 + 21*k" (вспомните решение тригонометрических уравнений), хитрые бандюги-математики имеют дело с их "представителями": 2, -19 ...
Фишка в том, что любое действие с исходными числами однозначно переносится на действия с "представителями". А для них вот выполняются равенства, которые я привел выше.
Голову я вам не совсем заморочил?
Тут вам может быть поможет соображение Гермеса Трисмегиста: "Что наверху - то и внизу"
Наверху - числа. Внизу - остатки от деления (кольцо по модулю)
Остатки в арифметике по модулю - это как бы проекция истинных вычислений.
Надеюсь, что не очень вас утомил этой маленькой лекцией...

Добавлено через 6 минут

Сообщение от IGPIGP

f(a+b)=f(f(a)+f(b))

Эта формула не совсем верна (точнее, не верна вовсе, ибо бессмысленна(математически)), но именно ей мы, бедолаги-программисты, и пользуемся. Там чуток не так.
Но, впрочем, я не намерен далее испытывать ваше терпение на предмет своего занудства

IGPIGP · 05.06.2019, 00:24

Сообщение от Байт

Голову я вам не совсем заморочил?
Тут вам может быть поможет соображение Гермеса Трисмегиста: "Что наверху - то и внизу"
Наверху - числа. Внизу - остатки от деления (кольцо по модулю)
Остатки в арифметике по модулю - это как бы проекция истинных вычислений.

Для семи-класника, сойдёт.

IGPIGP · 05.06.2019, 10:01

Сообщение от IGPIGP

Для семи-класника

Вот что пришло на ум:
Вот это - легкий укол:

Сообщение от Байт

Математика там очень простая. Доступная любознательному семикласснику.

Принимается. Бандиты-математики любят начинать с фраз вроде "Легко заметить" и продолжить в виде:

Сообщение от Байт

К одному классу принадлежат числа, дающие одинаковый остаток на этот "модуль" (опять же, не путать с модулем, как абсолютной величиной, с функциями abs, fabs)
2, 23, 44, -19... - это все числа одного класса для модуля 21
Но чтобы не иметь дела с классами (множествами), ибо это утомительно писать "2 + 21*k" (вспомните решение тригонометрических уравнений), хитрые бандюги-математики имеют дело с их "представителями": 2, -19 ...
Фишка в том, что любое действие с исходными числами однозначно переносится на действия с "представителями". А для них вот выполняются равенства, которые я привел выше.
Голову я вам не совсем заморочил?
Тут вам может быть поможет соображение Гермеса Трисмегиста: "Что наверху - то и внизу"
Наверху - числа. Внизу - остатки от деления (кольцо по модулю)
Остатки в арифметике по модулю - это как бы проекция истинных вычислений.

Хочу остановиться на 2-х моментах:
1.

Сообщение от Байт

Сообщение от IGPIGP

f(a+b)=f(f(a)+f(b))

Эта формула не совсем верна (точнее, не верна вовсе, ибо бессмысленна(математически)), но именно ей мы, бедолаги-программисты, и пользуемся.

Байт, вы привели формулу

Сообщение от Байт

f(x+y) = f(x) + f(y)

далее вы говорите о том, что каждый из операнов - x,y - "представитель", а попросту - продукт действия операции. Но теряется же именно математический смысл, поэтому, что нельзя абстрагироваться от операции описывая её. То есть "бедолаги программисты" ближе к здравому смыслу и :
f(x+y) =f(f(x) + f(y)) - это то что работает.
Вот что получается для чисел a != b
f(a*b)=f(a+a+...+a)//b-раз складываем a и получаем:
f(f(a)+f(a)+...+f(a))
и
f(b*f(a))

Для степеней получается (у меня) вот как:
f(a^b)=f(a*f(a^b-1))
и это ключ к упрощению вычислений так как мы вычисляем ряд степеней 10-ки и можем использовать предыдущий результат.
2.

Сообщение от Байт

Для больших c все быстро рухнет. И даже не очень больших.

Вот этого не понял. В условии сказано;

Сообщение от NuMeRiC_

По данным a и c указать наименьшее значение b.

b - хоть оно и наименьшее но это и есть то число о котором речь. Оно получается дописыванием ряда чисел в виде цифр и для того чтобы его вывести не считая нужно либо строковое представление либо извратиться с последовательной печатью
составляющих чисел в строку. Тут может вы и правы. Тогда задача сводится к подсчёту количества добавочных чисел, а потом печать "разворачивает" последовательность в "вид" числа.
Если это так, то я снова поражаюсь отсутствием у математиков элементарной способности удерживать границы абстракции.
Ведь

Сообщение от NuMeRiC_

По данным a и c указать наименьшее значение b

Это не получить визуальное представление или распечатать последовательность цифр ... Это указать значение. Значение это число! И это число обладает свойствами чисел. Может быть операндом арифметической операции, например. Тогда, нужно получить значение? Но математики легко читают матрицы из файлов, удаляют элементы из массивов и делают ещё кучу чудес.

Байт · 05.06.2019, 23:52

Сообщение от IGPIGP

Вот это - легкий укол:
Сообщение от Байт
Математика там очень простая. Доступная любознательному семикласснику.

Простите великодушно. Просто я сужу по себе. Именно в состоянии семиклассника я эти штуки осваивал и решал. Возможно, я был излишне любознателен. Но так сложилось. В середине XX века картавый заика, да еще и еврей, имел мало шансов добиться уважения во дворе. Отрадой моей стал Кордемский. Ну а дальше все пошло уже само собой.

Сообщение от IGPIGP

математики ... делают ещё кучу чудес.

Как правило, для этих чудес у них есть четкие логические построения и обоснования.

Сообщение от IGPIGP

Это не получить визуальное представление или распечатать последовательность цифр ... Это указать значение.

Вы знаете, как ни странно, но я это понял сразу. Постановку задачи я понял. Просто один из путей (обозначенный в стартовом посте и в вашем посте 3) является именно выписыванием значения. Что не нужно. Можно все свести к арифметике по модулю. Что я и предложил.
Ликбез, который я пытался предпринять, признаюсь, был неудачен. Просто я знаю такие алгебраические понятия, как "кольцо", фактор-кольцо", "идеал", "смежные классы", "гомоморфизм" (узнал я их не в 7-м классе, а много позже, но основа для понимания этих чудес была заложена именно тогда) а вы, скорее всего, не очень. И беды здесь нет никакой. Как и чьегото превосходства.
Давайте послушаем кота Леопольда и других мудрых созданий...

IGPIGP · 06.06.2019, 02:33

Сообщение от Байт

Как правило, для этих чудес у них есть четкие логические построения и обоснования.

Я не имел ввиду великих математиков. Математика это база научного образа мысли. Я имел ввиду тех, кто считает, что удалить элемент массива, сохранить матрицу в файл или написать значение, это раз плюнуть. И этих намного больше чем первых. Что касается ликбеза и семи-классников, то "легко заметить", что моя шутка не была тяжелее вашей.

Что же касается фразы "указать значение", то она достаточно многозначна и возможно вы правы. Однако, я не люблю "хитрых" заданий. Потому что знаю множество задач, где без ребусов, а достаточно прозрачно сформулированное условие тем не менее требует серьёзных раздумий. А коли программисты пишут задачу и говорят о значении, то мне кажется естественным понимать под этим значение а не визуальное отображение. Я не спорю с тем, что задача в вашей интерпретации верна. Мне не нравится формулировка самой задачи.

Байт · 06.06.2019, 11:52

Сообщение от IGPIGP

f(x+y) =f(f(x) + f(y)) - это то что работает.

Попробую объяснить, почему эта формула неверна, точнее - бессмысленна. Хотя и работает. Если не получится, значит объяснятель я - никакой.

Вы наверное знаете, что функция определяется тремя вещами: Множеством (областью) определения, Множеством (областью) значений и Правилом, задающим для каждого элемента из области определения элемент-значение. При несовпадении хотя бы одной из этих вещей функции - разные.
Для нашей функции (f(x) - взятие остатка от деления x на, скажем, 3) Множество определения - все целые числа (обозначается обычно Z). Множество значений имеет 3 элемента, чтобы не путать, обозначим их a0, a1, a2 - множество M
Правило простое: f(x) = x%3
На множестве M естественным образом вводятся операции сложения и умножения
a0+a0= a0 a0+a1=a1 a0+a2=a2 a1+a1=a2 a1+a2=a0 a2+a2=a1
a0*a0=a0 a0*a1=a0 ... a2*a2=a1
И... большая удача! Функция f оказывается гомоморфизмом! Т.е. f(x+y)= f(x) + f(y) и f(x*y) = f(x)*f(y). Собственно,, мы для этого так определили операции. Но хочу обратить ваше внимание на то, что знаки операций в левых и правых частях этих равенств имеют совершенно разный смысл! Слева - привычные нам операции над целыми числами, справа - операции над элементами множества М, которые мы недавно определили.
Теперь возьмем вашу формулу и ее правую часть f(f(x) + f(y)). f(x) f(y) - элементы множества М. f(x)+f(y) - тоже. Он равен некоторому элементу $https://www.cyberforum.ru/cgi-bin/latex.cgi?a \in M$ Но этот a не принадлежит Z. И функцию f к нему применить нельзя! Она просто не определена!

Не по теме:

Фу, приустал, сейчас перекурю, и снова в бой:)

Добавлено через 32 минуты
В компьютере есть замечательный набор операций над целыми числами (Z). Но увы! нет операций над множеством М и ему подобными. Сложения и Умножения. Что же делать бедолаге-программисту? А все просто! Вместо a0, a1, a2 он берет ЛЮБОГО представителя уже из Z. И совершает операцию с ним. А потом "спускает" результат в М. Если взятие представителя обозначить как p(m), то ваша формула будет выглядеть так
f(x+y) = f(p(f(x)) + p((f(y)))
Поэтому в моем коде из поста 4 содержится так много процентиков.
И Алгебра гарантирует, что результат не зависит от выбора конкретного представителя.

ЗЫ. Вы спросите, зачем городить такие огороды. Но Алгебра имеет дело не только с целыми числами, а с множеством других объектов. Оказывается, что если эти объекты выполняют несколько простых аксиом (аксиом Кольца), то все это применимо и к ним. А при изучении всех этих абстракций большим подспорьем является Кольцо целых чисел и его Фактор-Кольца - множества остатков от деления. Ввиду своей простоты и интуитивной доступности даже для семикласника.

Добавлено через 3 минуты

Сообщение от Байт

В компьютере есть замечательный набор операций над целыми числами (Z)

В самом деле этот набор операций работает над кольцом остатков по модулю 2³². Но имея дело с небольшими числами, этого можно не заметить.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	03.06.2019, 22:14
	Сообщение было отмечено NuMeRiC_ как решение Решение NuMeRiC_, самая главная беда здесь в том, что образованное приписками число может оказаться довольно большим. и обычная арифметика с ним не справится. Хотя тут можно попытаться выкрутится, так как деление нам требуется по модулю c < 10000 Добавлено через 10 минут И, конечно, pow надо засунуть куда подальше подальше. Задача целочисленная, и нечего привлекать неточные функции работы с плавающими числами. Но, наверное, может помочь такое соображение (xy +z) % c математически равно (((x%c)(y%c))%c + z%c)%c - гомоморфизм кольца целых чисел на кольцо вычетов по модулю. И вот это соображение позволит обойтись без длинной арифметики. Как-бы алгоритм просматривается, но глаза слипаются... 2

Указать наименьшее значение, которое делится на число составленное из последовательности цифр

Решение