{"id":852,"date":"2020-03-24T22:52:24","date_gmt":"2020-03-25T05:52:24","guid":{"rendered":"http:\/\/209.126.2.187\/?p=852"},"modified":"2020-05-16T10:54:58","modified_gmt":"2020-05-16T17:54:58","slug":"divisors-factors","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2020\/03\/24\/divisors-factors\/","title":{"rendered":"Divisors &#038; Factors"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">Summary<\/h2>\n\n\n\n<p>In this post, I will introduce some common techniques related to divisors and factors.\u00a0<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Details<\/h2>\n\n\n\n<h4 class=\"wp-block-heading\">Number of Divisors<\/h4>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">\/\/ O(sqrt(n))\nint count_divisors(int n) { \n     int cnt = 0; \n     for (int i = 1; i * i &lt;= n; i++) { \n         if (n % i == 0) { \n             if (n \/ i == i) { \/\/ note this\n                 cnt++; \n             }\n             else { \n                 cnt += 2; \n             }\n         } \n     } \n     return cnt\n }<\/code><\/pre>\n\n\n\n<h4 class=\"wp-block-heading\">GCD<\/h4>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">\/\/ gcd(0, b) = b\n\/\/ gcd(a, b), b > a &lt;=> gcd(b - a, b) &lt;=> gcd(b % a, a) \n\n\/\/ O(h), h => # digits\nint gcd(int a, int b) {\n  if (a > b) swap(a,b);\n  if (a == 0) return b;\n  return gcd(b%a, a);\n}<\/code><\/pre>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Summary In this post, I will introduce some common techniques related to divisors and factors.\u00a0 Details Number of Divisors GCD<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,49],"tags":[],"class_list":["post-852","post","type-post","status-publish","format-standard","hentry","category-alg","category-math"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/852","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/comments?post=852"}],"version-history":[{"count":4,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/852\/revisions"}],"predecessor-version":[{"id":1237,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/852\/revisions\/1237"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=852"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=852"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=852"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}