Base-10에서 모든 완전 제곱은 0 , 1 , 4 , 5 , 6 또는 9로 끝납니다 .

Base-16에서 모든 완벽한 제곱은 0 , 1 , 4 또는 9로 끝납니다 .

Nilknarf는 이것이 왜 그리고이 답변 에서 이것을 잘 해결하는 방법을 설명하지만 여기에 간단한 설명도 제공합니다.

Base-10 숫자 N을 제곱 할 때 “1”자릿수는 “십”자릿수 또는 “100”자릿수 등의 영향을받지 않습니다. 만에 “사람”숫자 N은 의 “사람”자리에 영향을 N ⁽²⁾ 쉬운 (그러나 아마 golfiest를) 방법은 모든 가능한 마지막 자리를 찾을 수 있도록하기위한, N ^2를 찾는 것입니다 n은 ² 모드 (10)는 모두 0 <= N < 10 . 각 결과는 가능한 마지막 숫자입니다. Base-m의 경우 모든 0 <= n < m에 대해 n ² mod m 을 찾을 수 있습니다.

입력 N이 주어지면 Base-N의 완벽한 제곱을 위해 가능한 모든 마지막 숫자를 출력 하는 프로그램을 작성하십시오 (중복없이). 당신은 가정 할 수 N이 보다 큰 공 , 그리고 N는 것을 작은 충분 N ² 오버 플로우 (당신이 모든 방법을 테스트 할 수 있습니다하지 않을 경우 N ^(2)는 , 내가 당신에게 브라우니 점의 유한 한 양을 줄 것이다하지만 알고 브라우니 포인트와 실제 포인트의 환율은 1에 무한대입니다.

테스트 :

 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 이므로 표준 규칙이 적용됩니다!

(: 당신은 너무 쉽게이를 발견 한 경우, 또는 당신은이 질문에 고려 주제에 대한보다 깊이있는 질문을 할 직각의 차 잔류 물 시험을위한 기지의 최소 덮개 ).

답변

R²%³Q

R²%³Q   Main link, argument: n

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

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

Lns%ê

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

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

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

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)))

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)))

{%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