Pascal. Как проверить, что введенное число, которое больше MaxInt, является кратным 6?

Question

Подскажите, пожалуйста, как работать с числами, которые больше MaxInt? Нужно проверить, кратно ли такое число 6. Не совсем понимаю, как это реализовать.

Answer 1

во-первых вам надо написать свой функционал для таких чисел

такие большие числа могут представлять собой массив обычных чисел - например INT - это 4 байта (т.е. от 0 до 2^32), а два таких числа дают уже 8 байт (т.е. от 0 до 2^64) и т.д.

идем дальше

для того, чтобы узнать что огромное число делится на 6 нам понадобится такая вещь как основная теорема арифметики:

одно из ее следствий - если число делится на взаимно простые числа, то оно делится и на произведение этих чисел

числа 2 и 3 - взаимно простые, значит нам для определения делимости на 6 надо проверить делится ли ваше огромное число на 2 и на 3

делимость на 2:

если ваше большое число состоит из a,b,c,d,...,z чисел типа INT, то достаточно проверить, что последнее число z - чётное

делимость на 3:

проверять сумму цифр на делимость на 3 не стоит, можно обойтись более простым подходом - сумма остатков деления чисел a,b,c,d,...,z, которые составляют большое число, должно делиться на 3 без остатка (т.е. сумма остатков должна быть 0)

т.е. надо будет (a mod 3 + b mod 3 + ... + z mod 3) mod 3 = 0 проверить

Answer 2

Чтобы "собрать" число из цифр надо начать с нуля и для каждой цифры умножать число на десять и добавлять значение цифры. Для цифр '12345':

цифра	n
	0
'1'	10·0 + 1 = 1
'2'	10·1 + 2 = 12
'3'	10·12 + 3 = 123
'4'	10·123 + 4 = 1234
'5'	10·1234 + 5 = 12345

Если продолжать достаточно долго на Паскале, значение n перестанет помещаться в целочисленную переменную и результат будет испорчен переполнением. Нам нужно не само значение n, а только его остаток по модулю 6. Перепишем весь алгоритм на остатках:

цифра	n mod 6
	0
'1'	10·0 + 1 = 1 ≡ 1 mod 6
'2'	10·1 + 2 = 12 ≡ 0 mod 6
'3'	10·0 + 3 ≡ 3 mod 6
'4'	10·3 + 4 ≡ 4 mod 6
'5'	10·4 + 5 ≡ 3 mod 6

В таком виде мы храним текущий остаток вместо всего числа, переполнения невозможны.

var
  c: char;
  digit: integer;
  reminder: integer;
begin
  reminder := 0;
  while True do
    begin
      read(c);
      if (c < '0') or ('9' < c) then
        break;
      digit := ord(c) - ord('0');
      reminder := (10 * reminder + digit) mod 6;
    end;
  writeln(reminder);
end.

$ fpc mod6.pas
Free Pascal Compiler version 3.0.0+dfsg-2 [2016/01/28] for x86_64
Copyright (c) 1993-2015 by Florian Klaempfl and others
Target OS: Linux for x86-64
Compiling temp.pas
Linking temp
/usr/bin/ld.bfd: warning: link.res contains output sections; did you forget -T?
16 lines compiled, 0.0 sec

$ echo 12345 | ./mod6
3

$ echo 1234567890123456789012345789012345678901234567890123457890 | ./mod6
0

БЛОГ НА HUSL

Pascal. Как проверить, что введенное число, которое больше MaxInt, является кратным 6?

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