Diberikan dua input q nmenentukan apakah qresidu kuadratik n.

Yaitu, adakah di xmana x**2 == q (mod n)atau qmod persegi n?

Memasukkan

Dua bilangan bulat qdan n, di mana qdan nadalah bilangan bulat apa pun 0 <= q < n.

Keluaran

Kebenaran atau kebohongan.

Secara opsional, cetak semua (atau semua) xyang adax**2 == q (mod n)

Contohnya

>>> quadratic_residue(1, 5)
True
>>> quadratic_residue(3, 8)
False
>>> quadratic_residue(15, 22)
True

Aturan

Kode Anda harus berupa program atau fungsi. Masukan bisa dalam urutan apa pun. Ini adalah kode golf, jadi kode terpendek dalam byte menang.

Jika ada yang tidak jelas atau perlu diperbaiki, beri tahu saya.

Bonus

• Bonus 2-byte jika fungsi Anda menerima qbilangan bulat sembarang.

Katalog

var QUESTION_ID=65329;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk";var OVERRIDE_USER=47581;var answers=[],answers_hash,answer_ids,answer_page=1,more_answers=true,comment_page;function answersUrl(index){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(index,answers){return"http://api.stackexchange.com/2.2/answers/"+answers.join(';')+"/comments?page="+index+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){answers.push.apply(answers,data.items);answers_hash=[];answer_ids=[];data.items.forEach(function(a){a.comments=[];var id=+a.share_link.match(/\d+/);answer_ids.push(id);answers_hash[id]=a});if(!data.has_more)more_answers=false;comment_page=1;getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:true,success:function(data){data.items.forEach(function(c){if(c.owner.user_id===OVERRIDE_USER)answers_hash[c.post_id].comments.push(c)});if(data.has_more)getComments();else if(more_answers)getAnswers();else process()}})}getAnswers();var SCORE_REG=/<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;var OVERRIDE_REG=/^Override\s*header:\s*/i;function getAuthorName(a){return a.owner.display_name}function process(){var valid=[];answers.forEach(function(a){var body=a.body;a.comments.forEach(function(c){if(OVERRIDE_REG.test(c.body))body='<h1>'+c.body.replace(OVERRIDE_REG,'')+'</h1>'});var match=body.match(SCORE_REG);if(match)valid.push({user:getAuthorName(a),size:+match[2],language:match[1],link:a.share_link,});else console.log(body)});valid.sort(function(a,b){var aB=a.size,bB=b.size;return aB-bB});var languages={};var place=1;var lastSize=null;var lastPlace=1;valid.forEach(function(a){if(a.size!=lastSize)lastPlace=place;lastSize=a.size;++place;var answer=jQuery("#answer-template").html();answer=answer.replace("{{PLACE}}",lastPlace+".").replace("{{NAME}}",a.user).replace("{{LANGUAGE}}",a.language).replace("{{SIZE}}",a.size).replace("{{LINK}}",a.link);answer=jQuery(answer);jQuery("#answers").append(answer);var lang=a.language;lang=jQuery('<a>'+lang+'</a>').text();languages[lang]=languages[lang]||{lang:a.language,lang_raw:lang.toLowerCase(),user:a.user,size:a.size,link:a.link}});var langs=[];for(var lang in languages)if(languages.hasOwnProperty(lang))langs.push(languages[lang]);langs.sort(function(a,b){if(a.lang_raw>b.lang_raw)return 1;if(a.lang_raw<b.lang_raw)return-1;return 0});for(var i=0;i<langs.length;++i){var language=jQuery("#language-template").html();var lang=langs[i];language=language.replace("{{LANGUAGE}}",lang.lang).replace("{{NAME}}",lang.user).replace("{{SIZE}}",lang.size).replace("{{LINK}}",lang.link);language=jQuery(language);jQuery("#languages").append(language)}}

body{text-align:left!important}#answer-list{padding:10px;width:290px;float:left}#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table>

Pyth, 9 byte

}Em%*ddQQ

Cobalah online: Demonstrasi atau Test Suite

Penjelasan:

}Em%*ddQQ   implicit: Q = first input number
  m     Q   map all numbers d of [0, 1, ..., Q-1] to:
    *dd       d*d
   %   Q      mod Q
            this gives the list of all quadratic residues
 E          read another input number
}           check, if it appears in the list of quadratic residues

Mathematica, 25 byte

AtomQ@PowerMod[#,1/2,#2]&

Mathematica, menjadi Mathematica, secara alami memiliki dasar untuk menghitung modul modul, melalui PowerMod. Jika ada solusi, solusi layak terkecil dikembalikan, jika tidak, ekspresi asli (ditambah pesan).

Untuk mendapatkan hasil sebenarnya / palsu, kami melewatkan hasilnya AtomQ, yang memeriksa apakah ekspresi dapat dipecah. Bilangan bulat atom, kembali True, sementara non-atom PowerMod[q,1/2,n]kembaliFalse

Terima kasih kepada @ MartinBüttner untuk tips golf dan fungsi berburu bersama saya.

Par , 11 9 byte

✶X[²x%)↔,

Setiap karakter hanya menggunakan satu byte; Lihat di sini .

Penjelasan

✶              ## Read two numbers
X              ## Assign second to x
[              ## Map
 ²             ## Square
 x%            ## Mod x
)              ## 
↔              ## Swap
,              ## Count

Dihapus dua byte berkat Jakube.

LabVIEW, 16 15 byte Setara

Dihitung menurut meta post saya .

Haskell, 31 byte

Disimpan 3 byte berkat Martin Büttner.

q#n=elem q[mod(x^2)n|x<-[1..n]]

Matlab, 29

Fungsi ini mengkuadratkan semua angka dari 0 hingga n dan memeriksa apakah kuadrat minus q adalah nol mod n.

@(q,n)any(~mod((0:n).^2-q,n))

Prolog (SWI), 34 byte

Kode:

Q*N:-between(0,N,X),X*X mod N=:=Q.

Penjelasan:
Memeriksa apakah bujur sangkar antara 0 dan N meninggalkan Q saat dibagi dengan N .

Contoh:

3*8.
false

15*22.
true

Cobalah online di sini

CJam, 11 byte

{_,2f#\f%&}

Blok yang tidak disebutkan namanya ini mengharapkan q npada tumpukan dan meninggalkan [q]pada tumpukan sebagai nilai kebenaran atau ""sebagai nilai palsu.

Uji di sini.

Kredit untuk Sp3000 yang juga datang dengan solusi ini tetapi "tidak bisa diganggu posting".

Penjelasan

_,  e# Duplicate n and turn into range [0 1 ... n-1]
2f# e# Square each element in the range.
\f% e# Take each element in the range modulo n.
&   e# Set intersection with q to check if any square yields q (mod n).

J, 9 byte

e.]|i.^2:

Pemakaian:

   1 (e.]|i.^2:) 5
1
   3 (e.]|i.^2:) 8
0
   15 (e.]|i.^2:) 22
1

Penjelasan:

e.]|i.^2:
    i.    [0..N-1]
      ^   to the power of
       2: 2 (constant 2 function)
  ]|      mod N       
e.        contains Q? (0/1 result)

Beberapa J mekanik trivia:

Fungsi dikelompokkan oleh 3 iteratif dari kanan dan jika ada satu kiri, seperti dalam kasus kami ( e. (] | (i. ^ 2:))), bagian yang dikelompokkan disebut dengan argumen kanan ( N) dan fungsi kiri ( e., "berisi") disebut dengan kiri asli argumen ( Q) dan hasil dari bagian yang dikelompokkan.

( e.]|i.*i.dan e.]|2^~i.juga menyelesaikan masalah dengan panjang yang sama.)

Cobalah online di sini.

Mathematica, 27 byte

PowerModList[#,1/2,#2]!={}&

Pemakaian:

In[1]:= PowerModList[#,1/2,#2]!={}&[1,5]

Out[1]= True

Javascript ES6, 42 byte

(q,n)=>[...Array(n)].some((x,y)=>y*y%n==q)

Kredit ke @apsilers untuk byte serius disimpan!

Serius , 20 byte

,;R@,;╗@%╝`ª╜@%╛=`MΣ

Mengambil input pada dua baris:, qlalu n. Output yang 0jika qtidak residu kuadrat n, yang lain angka positif yang mewakili berapa banyak xdi [1, q](inklusif) memuaskan x^2 = q (mod n).

Cobalah secara online (permalink memiliki lebih banyak masalah, tetapi sementara itu Anda dapat menyalin dan menempelkan kode ke halaman kosong )

Penjelasan:

,;R      get q input, duplicate, push range(1, q+1)
@,;╗     move the list to the back of the stack, get n input, dupe, save in reg 0
@%╝      calculate q mod n and save to reg 1
`ª╜@%╛=` push this function:
  ª╜@%     square top of stack, push reg 0 value (n), swap, and mod
  ╛=       push reg 1 value (q mod n), compare equality (1 if equal else 0)
MΣ       map the function across the range, add results

Python 3, 41 40 byte

Mengambil qdan ndan menentukan apakah qada dalam daftar kotak dari 0kuadrat ke n-1kuadrat.

lambda q,n:q in[i*i%n for i in range(n)]

Ruby, 33 31 byte

Disimpan dua byte berkat Vasu Adari.

->q,n{(1..n).any?{|e|e*e%n==q}}

Seperti biasa, Ruby tidak akan mengalahkan bahasa golf mana pun, tetapi penampilannya bagus di sini.

Julia, 30 byte

f(q,n)=q∈[i^2%n for i=0:n-1]

Ini sebuah fungsi f yang menerima dua bilangan bulat dan mengembalikan boolean.

Tidak Disatukan:

function f(q::Integer, n::Integer)
    # Generate an array of quadratic residues
    x = [i^2 % n for i = 0:n-1]

    # Determine whether q is one of these values
    return q ∈ x
end

JavaScript (ES6), 43 byte

(q,n)=>eval('for(x=n,r=0;x--;)r+=x*x%n==q')

Penjelasan

(q,n)=>
  eval(`              // eval allows us to use a for loop without {} or return
    for(x=n,r=0;x--;) // iterate over all possible values of x
      r+=x*x%n==q     // r = the number of matching x values
  `)                  // implicit: return r

Uji

q = <input type="number" id="Q" /><br />
n = <input type="number" id="N" /><br />
<button onclick="result.innerHTML=(

(q,n)=>eval('for(x=n,r=0;x--;)r+=x*x%n==q')

)(+Q.value,+N.value)">Go</button><pre id="result"></pre>

𝔼𝕊𝕄𝕚𝕟, 13 karakter / 25 byte

⟦Ѧí]ĉ⇀_²%í≔î)

Try it here (Firefox only).

Japt, 10 byte

Vo d_²%V¥U

Golf Japt resmi pertama saya! Terima kasih kepada @ETHProductions untuk menghemat satu byte!

Tidak Terikat / Penjelasan

Vo d_  ²  %V¥ U
Vo dZ{Zp2 %V==U}  // implicit: U,V = inputs
Vo                // Create a range from 0 to n-1
   dZ{         }  // Check if any element Z in the range satisfies the condition:
       Zp2        // Is Z squared...
           %V     // modulo n...
             ==U  // equal to q?
                  // implicit output

Cobalah online!

C # 6 (.Net Framework 4.6) di LinqPad, 60 Bytes

bool b(int q,int n)=>Enumerable.Range(1,n).Any(y=>y*y%n==q);

Bima Sakti 1.0.2 , 41 byte

:>&{~1-:2h<:>n>;:>;<<b?{_a0_^}~;?{_0_1}}!

Ini mengharapkan qdan nhanya di stack. Ini output 1atau 0untuk kebenaran dan nilai-nilai palsu, masing-masing.

Pari / GP , 25 byte

(q,n)->issquare(Mod(q,n))

Cobalah online!

JavaScript (Node.js) , 33 byte

q=>n=>f=(t=n)=>t&&f(t-1)|t*t%n==q

Cobalah online!

Kenapa tidak ada yang melakukan ini