Отношения конгруэнтности

11

С учетом трех положительных целых чисел a, bи n(чьи максимальные значения являются максимальным представимым целочисленным значением в вашем языке) выведите истинное значение if a ≡ b (mod n)и false в противном случае. Для тех, кто не знаком с отношениями конгруэнтности, a ≡ b (mod n)это верно, если a mod n = b mod n(или, что эквивалентно, (a - b) mod n = 0)

ограничения

  • Встроенные методы проверки соответствия запрещены
  • Встроенные операции по модулю запрещены (это включает в себя такие операции, как divmodфункция Python , которая возвращает как частное, так и остаток, а также функции делимости, системные функции вычетов и т. П.)

Тестовые случаи

(1, 2, 3) -> False
(2, 4, 2) -> True
(3, 9, 10) -> False
(25, 45, 20) -> True
(4, 5, 1) -> True
(83, 73, 59) -> False
(70, 79, 29) -> False
(16, 44, 86) -> False
(28, 78, 5) -> True
(73, 31, 14) -> True
(9, 9, 88) -> True
(20, 7, 82) -> False

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

Mego
источник
Как насчет делимых функций?
Конор О'Брайен
@ CᴏɴᴏʀO'Bʀɪᴇɴ Эти работы проверяют остатки, поэтому они также запрещены. Я уточню.
Мего
Как насчет целочисленного деления полов в Python 2 /?
xnor
Деление с плавающей точкой?
El'endia Starman
1
База конверсии?
Деннис

Ответы:

4

Python 2, 27 байт

lambda a,b,n:(a-b)/n*n==a-b

Проверяет, a-bявляется ли кратное, nпутем деления на n, которое автоматически определяет этаж, и определяет, nдает ли умножение обратно на тот же результат.

XNOR
источник
4

Юлия, 24 байта

f(a,b,n,t=a-b)=t÷n==t/n

Это функция, которая принимает три целых числа и возвращает логическое значение.

Мы просто проверяем, равно ли целое число a - b, деленное на n, числу a - b, деленному на n . Это будет верно, когда нет остатка от деления, то есть a - b | n , что означает, что a - b (mod n ) = 0.

Алекс А.
источник
4

Pyth, 7 байт

!@UQ-FE

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

  UQ         range(first line). [0,...,Q-1]
    -FE      Fold subtraction over the second line.
 @           Cyclic index UQ at -FE
!            Logical NOT
lirtosiast
источник
3

Haskell, 23 байта

(a#b)n=div(a-b)n*n==a-b

Пример использования: (28#78)5-> True.

Тот же метод, что и в ответе @ xnor .

Ними
источник
3

Минколанг 0,15 , 14 11 байт

nn-n$d:*=N.

Попробуй это здесь! Ввод ожидается как a b n.

Объяснение:

n              Take number from input -> a
 n             Take number from input -> a, b
  -            Subtract               -> a-b
   n           Take number from input -> a-b, n
    $d         Duplicate stack        -> a-b, n, a-b, n
      :        Integer division       -> a-b, n, (a-b)//n
       *       Multiply               -> a-b, (a-b)//n*n
        =      1 if equal, 0 otherwise
         N.    Output as number and stop.
El'ndia Starman
источник
3

MATL , 9 байт

Sdt:i*0hm

Формат ввода

[a b]
n

Попробуйте онлайн!

S     % implicitly input [a, b]. Sort this array
d     % compute difference. Gives abs(a-b)
t:    % duplicate and generate vector [1,2,...,abs(a-b)]; or [] if a==b
i*    % input n and multiply to obtain [n,2*n,...,abs(a-b)*n]; or []
0h    % concatenate element 0
m     % ismember function. Implicitly display
Луис Мендо
источник
2

APL, 15 байт

{(⌊d)=d←⍺÷⍨-/⍵}

Это двоичная функция, которая принимает n слева и a и b как массив справа.

Подход здесь в основном такой же, как в моем ответе Юлии . Мы проверяем, равен ли a - b / n полу самого себя, что будет верно, если a - b (mod n ) = 0.

Алекс А.
источник
Спасите четыре:d=⌊d←⎕÷⍨-/⎕
Адам
2

JavaScript (ES6), 27 байт

@ CᴏɴᴏʀO'Bʀɪᴇɴ опубликовал версию, которая не работает; Вот «общий алгоритм», который люди используют в форме, которая «работает»:

(a,b,n)=>n*(0|(a-b)/n)==a-b

Слово «works» находится в пугающих кавычках, потому что ярлык, который мы используем для Math.floor()неявного усечения числа, должно быть в 32-битном диапазоне со знаком, поэтому он не может обработать полное 52-битное или целое пространство целых чисел, которое может JavaScript описать.

ЧР Дрост
источник
Если этот ответ не может обработать все представимые положительные целые числа в языке, он недействителен.
Мего
1
@Mego: Учитывая, что некоторые языки будут использовать 32-битные целые числа, я думаю, что ограничение является произвольно произвольным, если только вы не укажете либо битовую ширину целых чисел, либо в том, что язык должен иметь bignums.
ЧР Дрост
1
Это совсем не произвольно. В задаче четко указано, что входными данными могут быть любые 3 положительных целых числа, вплоть до максимального представимого целочисленного значения на выбранном языке. Если отправка может быть неудачной для набора входов в этом диапазоне, это недопустимо. Соответствующий мета пост .
Мего
@Mego: Позвольте мне прямо спросить вас: собираетесь ли вы возражать против решения на Haskell по тому же критерию? (Решение Haskell является полиморфным, поскольку оно не имеет сигнатуры и не записано таким образом, чтобы вызывать ограничение страшного мономорфизма. Для нормальных типов со знаком оно отлично работает во всем диапазоне; однако существует набор входных данных, которые вы можете вставьте - тестовый набор: заданный (2, 150, 3) :: (Word8, Word8, Word8)вами критерий явно «если теоретически существует вход, который делает ответ недействительным, ответ следует считать недействительным».)
CR Drost
1
@Mego: Если вам интересно, почему я так много делаю из этого, числовой тип JavaScript содержит непрерывные целые числа вокруг полос 2 ^ 52, так что становится вполне вероятным, что (a - b) == aдля определенных значений a. Ответ, который должен быть действителен в этих пограничных областях, почти невозможен, даже если я беру штраф за байты и заменяю (0|...)наMath.floor(...).
CR Drost
2

CJam, 7 байтов

l~-\,=!

Порядок ввода есть n a b.

Проверьте это здесь.

объяснение

l~  e# Read input and evaluate to push n, a and b onto the stack.
-   e# Subtract b from a.
\,  e# Swap with n and turn into range [0 1 ... n-1].
=   e# Get (a-b)th element from that range, which uses cyclic indexing. This is
    e# equivalent to modulo, and as opposed to the built-in % it also works correctly
    e# for negative (a-b).
!   e# Negate, because a 0 result from the previous computation means they are congruent.
Мартин Эндер
источник
1

Python 3, 27 байт

lambda a,b,n:pow(a-b,1,n)<1

pow(x,y,n)рассчитывает (x**y)%n, так что это просто (a-b)**1%n.

lirtosiast
источник
1

ES6, 28 байт

(a,b,n)=>!/\./.test((a-b)/n)

Работает, ища десятичную точку в (ab) / n, которая, я надеюсь, разрешена.

Нил
источник
1

Серьезно, 10 байт

,,,-A│\)/=

Принимает ввод как N\nA\nB\n(заглавные буквы используются для отличия от новой строки).

Попробуйте онлайн

Это использует тот же метод, что и ответ @ AlexA

Пояснение (заглавные буквы используются в качестве имен переменных для пояснительных целей):

,,,-A│\)/=
,,,         push N, A, B
   -A       push C = abs(A-B)
     │      duplicate entire stack (result is [N, C, N, C])
      \)/=  1 if C//N == C/N (floored division equals float division)
Mego
источник