20

В Base-10 все совершенные квадраты заканчиваются на 0 , 1 , 4 , 5 , 6 или 9 .

В Base-16 все совершенные квадраты заканчиваются на 0 , 1 , 4 или 9 .

Нилькнарф описывает, почему это так и как это очень хорошо решить в этом ответе, но я также дам краткое описание здесь:

При возведении в квадрат числа Base-10, N , цифра «единицы» не зависит от того, что находится в цифре «десятки» или цифры «сотни» и так далее. Только цифра «единицы» в N влияет на цифру «единицы» в N ² , поэтому простой (но, возможно, не самый удачный) способ найти все возможные последние цифры для N ² - это найти n ² mod 10 для всех 0 <= n < 10 . Каждый результат является возможной последней цифрой. Для Base-m вы можете найти n ² mod m для всех 0 <= n < m .

Напишите программу, которая при вводе N выводит все возможные последние цифры для идеального квадрата в Base-N (без дубликатов). Вы можете предположить, что N больше 0 , и что N достаточно мало, чтобы N ² не переполнялся (Если вы можете протестировать весь путь до N ² , я дам вам конечное количество очков брауни, но знайте, что обменный курс брауни-баллов к реальным баллам равен бесконечности до единицы).

тесты:

 Input -> Output
 1     -> 0
 2     -> 0,1
 10    -> 0,1,5,6,4,9
 16    -> 0,1,4,9
 31    -> 0,1,2,4,5,7,8,9,10,14,16,18,19,20,25,28
 120   -> 0,1,4,9,16,24,25,36,40,49,60,64,76,81,84,96,100,105

это код-гольф , поэтому применяются стандартные правила!

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

code-golf number-theory abstract-algebra Лорд фаркуаад
источник

1

Нужно ли сортировать выходной массив?

Лохматый

@ Шэгги Нету! Мего, Дублирование не допускается. Теоретически, N может быть огромным, поэтому дубликаты могут сделать вывод довольно нечитаемым. Я отвечу на вопрос

Лорд Фаркваад

Является ли вывод набора приемлемым?

полностью человек

2

@totallyhuman Почему это не будет действительным? Наборы являются неупорядоченными коллекциями, и их нельзя сортировать , так что ...

Mr. Xcoder

8

Желе , 5 байт

R²%³Q

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

объяснение

R²%³Q   Main link, argument: n

R       Range from 1 to n
 ²      Square each
  %³    Mod each by n
    Q   Deduplicate

Бизнес Кот
источник

19

Google Sheets, 52 51 47 байт

=ArrayFormula(Join(",",Unique(Mod(Row(A:A)^2,A1

_{^{Сохранено 4 байта благодаря Тейлору Скотту}}

Листы автоматически добавят 4 закрывающие скобки в конец формулы.

Он не возвращает результаты в порядке возрастания, но возвращает правильные результаты.

Инженер Тост
источник

Святая корова, человек, который является убийцей! Кто бы мог подумать? +1

bearacuda13

1

Это, безусловно, мой любимый ответ до сих пор.

Лорд Фаркваад

@LordFarquaad Я удивлен и рад, что это было так хорошо принято. Я пытался больше играть в гольф в Sheets и Excel, хотя - и частично потому, что - у них такие ограниченные диапазоны. Это привело к множеству формул массива.

Тост инженера

Вы должны быть в состоянии отбросить завершающие )s для -4 байта

Тейлор Скотт

@TaylorScott Спасибо! Я где-то недавно видел этот трюк - возможно, в одном из ваших ответов - и мне нужно помнить, чтобы начать его использовать.

Тост инженера

6

05AB1E , 5 байтов

Lns%ê

Попробуйте онлайн! или как тестовый набор

L     # Range 1 .. input
 n    # Square each
  s%  # Mod by input
    ê # Uniquify (also sorts as a bonus)

Райли
источник

Как sздесь работает? Повторяется ли ввод?

Луис Мендо

@LuisMendo sэто pop a,b; push b,a. Когда команда пытается извлечь что-то из стека и ничего не осталось, используется следующий ввод. Если больше нет ввода, используется последний ввод ( вот пример ). В этом случае я мог бы использовать тот, ¹который выдвигает первый ввод, но sлучше работает для набора тестов.

Райли

Благодарю. У вас есть больше информации относительно критерия, по которому вход повторно используется? (если было, скажем, три входа, и вы пытаетесь извлечь два значения из пустого стека)?

Луис Мендо

1

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

Райли

@LuisMendo Ln¹%êздесь эквивалентен. s,

Волшебная Урна Осьминога

6

Swift , 47 35 32 * байт

* -3 спасибо @Alexander.

Возможно, впервые в истории Swift ~~связи~~ обошли Python?

{m in Set((0..<m).map{$0*$0%m})}

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

объяснение

(0..<m).map{} - перебирает диапазон [0...m) и отображает следующие результаты:
$0*$0%m- квадрат каждого целого по модулю основания m.
Set(...) - удаляет дубликаты.
m in - назначает базу переменной m

Мистер Xcoder
источник

Имя пользователя проверено ... подождите секунду.

Рохан

1

Больше похоже на то, что он побеждает Python. Это впечатляет ! Я думал, что никогда не увижу того дня, когда это произойдет.

Калеб Клеветер

@CalebKleveter Спасибо! Я рад, что вы нашли это впечатляющим :)

Mr. Xcoder

3

C #, 63 байта

using System.Linq;m=>new int[m].Select((_,n)=>n*n%m).Distinct()

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

TheLethalCoder
источник

3

JavaScript (ES6), 52 байта

f=(m,k=m,x={})=>k?f(x[k*k%m]=m,k-1,x):Object.keys(x)

Контрольные примеры

Показать фрагмент кода

f=(m,k=m,x={})=>k?f(x[k*k%m]=m,k-1,x):Object.keys(x)

;[1, 2, 10, 16, 31, 120]
.map(m => console.log(m + ' -> ' + f(m)))

Развернуть фрагмент

Нерекурсивная версия, 60 58 байт

Сохранено 2 байта благодаря @ThePirateBay

m=>(a=[...Array(m).keys()]).filter(v=>a.some(n=>n*n%m==v))

Контрольные примеры

Показать фрагмент кода

let f =

m=>(a=[...Array(m).keys()]).filter(v=>a.some(n=>n*n%m==v))

;[1, 2, 10, 16, 31, 120]
.map(m => console.log(m + ' -> ' + f(m)))

Развернуть фрагмент

Arnauld
источник

Нерекурсивный 58 байт:m=>(a=[...Array(m).keys()]).filter(v=>a.some(n=>n*n%m==v))

@ThePirateBay Хороший улов. Благодарю.

Арно

3

Pyth, 6 байт

{%RQ*R

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

Как это устроено

{%RQ*RdQ    implicit variables
       Q    autoinitialized to eval(input())
    *R      over [0, …, Q-1], map d ↦ d times
      d         d
 %R         map d ↦ d modulo
   Q            Q
{           deduplicate

Андерс Касеорг
источник

3

Брахилог , 10 9 байт

>ℕ^₂;?%≜ᶠ

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

объяснение

       ≜ᶠ       Find all numbers satisfying those constraints:
    ;?%           It must be the result of X mod Input where X…
  ^₂              …is a square…
>ℕ                …of an integer in [0, …, Input - 1]

Fatalize
источник

Я собирался предложить {>≜^₂;?%}ᵘв качестве альтернативы ... потом я понял, что есть и отрицательные числа. > _ <

Эрик Outgolfer

1

@EriktheOutgolfer После того, как коммит получен в TIO, я могу фактически уменьшить этот ответ до 9 байтов, действительно используя ≜.

Фатализировать

Хорошо ... как это будет работать, если есть и отрицательные числа? Будет ли это просто игнорировать их или что-то?

Эрик Outgolfer

Мод @EriktheOutgolfer может быть определен как остаток от деления, который будет положительным (частное принимает знак). РЕДАКТИРОВАТЬ: также, квадраты являются положительными.

jaxad0127

@ jaxad0127 Я не думаю, что это имеет место здесь, так как >все равно учитывал бы отрицательные числа afaik.

Эрик Outgolfer

3

Japt , 7 6 байт

Ç²%UÃâ

Проверь это

1 байт спасен благодаря Оливеру

объяснение

Неявный ввод целого числа U.

Ç   Ã

Создайте массив целых чисел от 0до U-1, включительно и передавайте каждый через функцию.

²

Площадь.

%U

Модульное U.

â

Получить все уникальные элементы в массиве и неявно вывести результат.

мохнатый
источник

1

Я не думаю, что диапазон должен быть включающим. Ç²%UÃâКажется, работает просто отлично.

Оливер

2

Python 3 , 40 39 37 байт

-1 байт благодаря мистеру Xcoder. -2 байта благодаря Business Cat.

lambda m:[*{n*n%m for n in range(m)}]

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

totallyhuman
источник

1

Вы не можете заменить n**2на n*n?

г-н Xcoder

Да, всегда забывай это. > <Спасибо!

полностью человек

2

Кроме того, просто range(m)достаточно

Business Cat

1

Вы можете использовать наборы для 34 байтов

г-н Xcoder

2

Фактически , 11 байтов

;╗r⌠²╜@%⌡M╔

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

Объяснение:

;╗r⌠²╜@%⌡M╔
;╗           store a copy of m in register 0
  r          range(m)
   ⌠²╜@%⌡M   for n in range:
    ²          n**2
     ╜@%       mod m
          ╔  remove duplicates

Mego
источник

2

CJam , 12 байт

{_,_.*\f%_&}

Анонимный блок принимает номер и возвращает список.

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

объяснение

_,          Copy n and get the range [0 .. n-1]
  _.*       Multiply each element by itself (square each)
     \f%    Mod each by n
        _&  Deduplicate

Бизнес Кот
источник

Ницца! У меня было {:X{_*X%}%_&}по 13 байт

Луис Мендо

2

Haskell , 45 байт

import Data.List
f m=nub[n^2`mod`m|n<-[0..m]]

-4 байта от Андерса Касеорга

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

Mego
источник

К сожалению, бессмысленная версия f m=nub$map((`mod`m).(^2))[0..m]так же длинна, если только нет хитрого синтаксиса, чтобы избавиться от лишних скобок.

shooqie

2

МАТЛ , 6 5 байт

-1 байт благодаря @LuisMendo

:UG\u

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

Cinaski
источник

Благодарность! Я просмотрел документ в поисках этой функции, но не смог ее найти.

Чинаски

Кстати, у этого переводчика, созданного Suever, есть поиск документации, вы можете найти его полезным

Luis Mendo

1

Октава , 27 байт

@(n)unique(mod((1:n).^2,n))

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

Луис Мендо
источник

1

Mathematica, 30 байт

Union@Table[Mod[i^2,#],{i,#}]&

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

J42161217
источник

1

JavaScript (ES6), 48 байт

f=
n=>[...new Set([...Array(n)].map((_,i)=>i*i%n))]

<input type=number min=0 oninput=o.textContent=f(+this.value)><pre id=o>

Развернуть фрагмент

43 байта, если Setприемлем возврат массива вместо массива.

Нил
источник

1

Scala , 32 30 байт

Простое использование простого наконечника от OP.

(0 to n-1).map(x=>x*x%n).toSet

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

-2 байта благодаря @MrXcoder, с приоритетами (нет необходимости в () около* операции)

Интересно: возможно ли это неявно сказать компилятору, чтобы он понимал такие вещи, как (0 to n-1)map(x=>x*x%n)toSet(без необходимости import scala.language.postfixOps)?

В. Куртуа
источник

1

(0 to n-1).map(x=>x*x%n).toSetдля 30 байтов. Возведение в степень имеет более высокий приоритет, чем по модулю.

г-н Xcoder

@ Mr.Xcoder ооо ~ спасибо :)

В. Куртуа

1

Haskell , 44 байта

f m=[k|k<-[0..m],or[mod(n^2)m==k|n<-[0..m]]]

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

Андерс Касеорг
источник

0

Сетчатка , 70 байт

.+
$*

;$`¶$`
1(?=.*;(.*))|;1*
$1
(1+)(?=((.*¶)+\1)?$)

D`1*¶
^|1+
$.&

Попробуйте онлайн! Предупреждение: медленно для больших входов. Чуть быстрее 72-байтовая версия:

.+
$*

$'¶$';
1(?=.*;(.*))|;1*
$1
+s`^((1+)¶.*)\2
$1
^1+

D`1*¶
^|1+
$.&

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

Нил
источник

0

Clojure, 40 байт

#(set(map(fn[x](mod(* x x)%))(range %)))

MattPutnam
источник

0

Perl 6 , 19 байт

{set (^$_)»²X%$_}

Проверь это

Expanded:

{ # bare block lambda with implicit param ｢$_｣

  set        # turn the following into a Set (shorter than ｢unique｣)

      (
        ^$_  # a Range upto (and excluding) ｢$_｣
      )»²    # square each of them (possibly in parallel)

    X%       # cross modulus the squared values by

      $_     # the input
}

Брэд Гилберт b2gills
источник

0

Pyth , 13 байт

VQ aY.^N2Q){Y

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

Хромая попытка объяснить:

VQ               for N in [0 .. input-1]
                   blank space to supress implicit print inside the loop
     .^N2Q         N ^ 2 % input
   aY              append that to Y, which is initially an empty list
          )      end for
           {Y    deduplicate and implicit print

Чтобы отсортировать вывод, вставьте Sна любой стороне{

Я думаю, что должен быть более короткий путь ...

Alleks
источник

1

Да, функциональный стиль Pyth, как правило, гораздо более лаконичен . mapтвой друг!

Андерс Касеорг

0

Python 2 , 59 байт

t=int(input())
print list(set([(i*i)%t for i in range(t)]))

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

Хуснайн Раза
источник

0

PowerShell , 35 байт

0..($n="$args")|%{$_*$_%$n}|sort -u

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

детеныш
источник

0

R , 28 байт

unique((1:(n<-scan()))^2%%n)

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

Дрянная Монахиня
источник

0

Рубин ,31 30 байт

->m{(0..m).map{|n|n*n%m}.uniq}

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

Алексис Андерсен
источник

0

PHP , 53 байта

for(;$i<$t=$argv[1];)$a[$z=$i++**2%$t]++?:print"$z
";

Переходите от 0 к вводимому номеру, используя n^2 mod baseформулу для пометки номеров, которые были использованы. Он перемещается в эту позицию в массиве, проверяет, увеличен ли он, и выводит его, если нет. Затем он постепенно увеличивает его, чтобы дублированные значения не печатались.

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

Ксандерхолл
источник

0

8-е , 138 131 байт

Код

[] swap dup >r ( 2 ^ r@ n:mod a:push ) 1 rot loop rdrop ' n:cmp a:sort ' n:cmp >r -1 a:@ swap ( tuck r@ w:exec ) a:filter rdrop nip

объяснение

[] - Создать выходной массив

swap dup >r - Сохранить вход для последующего использования

( 2 ^ r@ n:mod a:push ) 1 rot loop - Вычислить квадратный конец

rdrop - Чистый р-стек

' n:cmp a:sort - Сортировать выходной массив

' n:cmp >r -1 a:@ swap ( tuck r@ w:exec ) a:filter rdrop nip - Избавиться от последовательных дубликатов из массива

SED (диаграмма эффекта стека) - это:a -- a

Использование и пример

: f [] swap dup >r ( 2 n:^ r@ n:mod a:push ) 1 rot loop rdrop ' n:cmp a:sort ' n:cmp >r -1 a:@ swap ( tuck r@ w:exec ) a:filter rdrop nip ;

ok> 120 f .
[0,1,4,9,16,24,25,36,40,49,60,64,76,81,84,96,100,105]

Chaos Manor
источник

0

Perl 5 , 41 + 1 (-n) = 42 байта

$k{$n++**2%$_}++while$n<$_;say for keys%k

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

Xcali
источник

Как заканчивается квадрат?

Ответы:

Желе , 5 байт

объяснение

Google Sheets, 52 51 47 байт

05AB1E , 5 байтов

Swift , 47 35 32 * байт

объяснение

C #, 63 байта

JavaScript (ES6), 52 байта

Контрольные примеры

Нерекурсивная версия, 60 58 байт

Контрольные примеры

Pyth, 6 байт

Как это устроено

Брахилог , 10 9 байт

объяснение

Japt , 7 6 байт

объяснение

Python 3 , 40 39 37 байт

Фактически , 11 байтов

CJam , 12 байт

объяснение

Haskell , 45 байт

МАТЛ , 6 5 байт

Октава , 27 байт

Mathematica, 30 байт

JavaScript (ES6), 48 байт

Scala , 32 30 байт

Haskell , 44 байта

Сетчатка , 70 байт

Clojure, 40 байт

Perl 6 , 19 байт

Expanded:

Pyth , 13 байт

Python 2 , 59 байт

PowerShell , 35 байт

R , 28 байт

Рубин ,31 30 байт

PHP , 53 байта

8-е , 138 131 байт

Perl 5 , 41 + 1 (-n) = 42 байта