{"id":729,"date":"2024-07-12T09:00:00","date_gmt":"2024-07-12T01:00:00","guid":{"rendered":"https:\/\/seanxd.com\/?p=729"},"modified":"2024-06-05T17:55:47","modified_gmt":"2024-06-05T09:55:47","slug":"zerojudge-j242","status":"publish","type":"post","link":"https:\/\/seanxd.com\/en\/zerojudge-j242\/","title":{"rendered":"ZeroJudge J242: Natural Number's Square Root"},"content":{"rendered":"<p class=\"translation-block\">Given a positive integer N, express 'sqrt(N)' in the format 'a sqrt(b)', where both a and b are positive integers, a\u00b2b = N, and b has no factors that are perfect squares, meaning for any natural number x, x\u00b2 does not divide b. For example: sqrt(12) = 2 sqrt(3), sqrt(15) = sqrt(15), sqrt(100) = 10.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Sample Inputs\/Outputs<\/h2>\n\n\n\n<figure class=\"wp-block-table nfd-wb-animate nfd-wb-fade-in-bottom-short\"><table class=\"has-fixed-layout\"><thead><tr><th>Sample Input(s)<\/th><th>Sample Output(s)<\/th><\/tr><\/thead><tbody><tr><td>Each test case consists of only one positive integer N (1 &lt; N &lt; 2<sup>31<\/sup>).<\/td><td class=\"translation-block\">The output format should be 'a sqrt(b)', and note the following:\n<br>\nIf a = 1, do not print a.\n<br>\nIf b = 1, do not print sqrt(b).\n<br>\nLeave a space between a and sqrt, and no spaces elsewhere.<\/td><\/tr><tr><td>12<\/td><td>2 sqrt(3)<\/td><\/tr><tr><td>15<\/td><td>sqrt(15)<\/td><\/tr><tr><td>100<\/td><td>10<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">Thought Process<\/h2>\n\n\n\n<p class=\"\">First, check if N is a perfect square. If pow(sqrt(N), 2) == N, it means N is a perfect square, so output sqrt(N) directly.<\/p>\n\n\n\n<p class=\"\">If N is not a perfect square, initialize two variables a = 1 and b = N, both of which need to be of type Long Long Int. Run a while loop, and inside it, run a for loop iterating through every perfect square. Declare a variable 'plus' initialized to 3, and write the for loop as follows: 'for (int i = 4; i &lt;= N; i += plus)&#039;, and after each iteration of the loop, increment &#039;plus&#039; by 2.<\/p>\n\n\n\n<p class=\"\">In the for loop, iterate only through perfect squares. Check if i is a factor of b. If i is a factor of N, then update b \/= i and a *= sqrt(i). If no factors are found in the current while loop iteration, break out of the while loop.<\/p>\n\n\n\n<p class=\"\">If a != 1, output a followed by a space character. Then output sqrt(b) after the conditional statement.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Sample Code\uff0d<a href=\"https:\/\/zerojudge.tw\/ShowProblem?problemid=j242\" target=\"_blank\" rel=\"noreferrer noopener\">ZeroJudge J242: Natural Number's Square Root<\/a><\/h3>\n\n\n\n<div class=\"hcb_wrap nfd-wb-animate nfd-wb-reveal-right nfd-delay-50\"><pre class=\"prism line-numbers lang-cpp\" data-lang=\"C++\"><code>#include &lt;iostream&gt;\n#include &lt;math.h&gt;\nusing namespace std;\n\nint main() {\n    cin.sync_with_stdio(0);\n    cin.tie(0);\n    long long int N;\n    cin &gt;&gt; N;\n    if (pow(int(sqrt(N)), 2) == N) cout &lt;&lt; sqrt(N) &lt;&lt; &quot;\\n&quot;;\n    else {\n        long long int a = 1, b = N;\n        bool stop = false;\n        while (!stop) {\n            stop = true;\n            long long int plus = 3;\n            for (long long int i = 4; i&lt;=N; i+=plus) {\n                if (b % i == 0) {\n                    b \/= i;\n                    a *= int(sqrt(i));\n                    stop = false;\n                }\n                plus += 2;\n            }\n        }\n        if (a != 1) cout &lt;&lt; a &lt;&lt; &quot; &quot;;\n        cout &lt;&lt; &quot;sqrt(&quot; &lt;&lt; b &lt;&lt; &quot;)\\n&quot;;\n    }\n}\n\n\/\/ZeroJudge J242\n\/\/Dr. SeanXD<\/code><\/pre><\/div>","protected":false},"excerpt":{"rendered":"<p>\u8f38\u5165\u6b63\u6574\u6578 N\uff0c\u5c07\u300csqrt(N)\u300d\u8f49\u63db\u6210\u300ca sqrt(b)\u300d\u4e4b\u683c\u5f0f\uff0c\u5176\u4e2d a \u8207 b \u90fd\u662f\u6b63\u6574\u6578\uff0ca2b  [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","footnotes":""},"categories":[29],"tags":[15,8,34,13,9],"class_list":["post-729","post","type-post","status-publish","format-standard","hentry","category-zerojudge-","tag-long-long-int","tag-8","tag-34","tag-13","tag-9"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/729","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/comments?post=729"}],"version-history":[{"count":2,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/729\/revisions"}],"predecessor-version":[{"id":734,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/729\/revisions\/734"}],"wp:attachment":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/media?parent=729"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/categories?post=729"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/tags?post=729"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}