… \u95ee [L, R] \u533a\u95f4\u4e2d\u6709\u591a\u5c11 \u56de\u6587^2-\u6570\u3002\u3002
\n\u56de\u6587^2-\u6570\u3002\u3002\u6ee1\u8db3\u5176\u662f\u5b8c\u5168\u5e73\u65b9\u6570\u3002\u3002\u4e14\u5176\u672c\u8eab\u548c\u5e73\u65b9\u6839\u5747\u4e3a\u56de\u6587\u6570\u3002\u3002
\n(L, R <= 10^100)\n\n<\/p>\n
..\u663e\u7136\u4e00\u8fdb\u6765\u5c31\u8981\u5bf9 L, R \u53d6 sqrt()\u3002\u3002
\n\u3002\u3002\u540e\u9762\u4e5f\u90fd\u662f\u53d6 sqrt() \u7684\u3002\u3002\u4ee5\u4e0b\u4ec5\u8003\u8651\u56de\u6587^2-\u6570\u7684\u5e73\u65b9\u6839\u3002
\n\u3002\u3002\u90a3\u4e48\u5c0f\u6570\u636e\u66b4\u529b\u4e00\u4e0b\u53ef\u4ee5\u53d1\u73b0\u8fd9\u4e9b\u6570\u7684\u6570\u5b57\u90fd\u662f 0,1,2,3 \u4e14\u51fa\u73b0 3 \u7684\u60c5\u51b5\u53ea\u6709\u5355\u72ec\u7684\u3002\u3002\u30023\u3002\u3002<\/p>\n
\u3002\u3002\u3002\u8fd9\u4e9b\u90fd\u4e0d\u662f\u672c\u8d28\u3002\u3002\u672c\u8d28\u662f\u6240\u6709\u6570\u4f4d\u548c\u7684\u5e73\u65b9\u548c\u8981\u6c42 < 10\u3002\u3002\u3002\u3002\u3002\n\n\u4ee5 131 \u4e3a\u4f8b\u3002\u3002\u3002\u3002\n\n\n\n
\r\n 131\r\n 393\r\n131\r\n\u2014\u2014\u2014\u2014\u2014\u2014\r\n16w61\r\n<\/pre>\n\u3002\u3002\u3002\u3002\u90a3\u4e48\u663e\u7136\u8fd9\u4e2a\u6761\u4ef6\u662f\u4e3a\u4e86\u9632\u6b62\u4e2d\u95f4\u90a3\u4e2a\u4f4d\u7f6e\u8fdb\u4f4d\u3002\u3002\u800c\u4e0d\u8fdb\u4f4d\u7684\u8bdd\u5c31\u53ef\u4ee5\u4fdd\u8bc1\u56de\u6587\u4e86\u3002\u3002\u3002<\/p>\n
\u3002\u3002\u4e8e\u662f\u6253\u8868\u5c31\u884c\u4e86\u3002\u3002\u3002<\/p>\n
\uff08 dfs() \u9884\u5904\u7406\u51fa\u6240\u6709 sqrt(10^100) \u4ee5\u5185\u7684\u56de\u6587^2-\u6570\u7684\u5e73\u65b9\u6839\u3002\u3002\u6392\u5e8f\u540e\u6bcf\u4e2a\u8be2\u95ee\u4e8c\u5206\u3002\u3002\u3002\u3002\uff09
\n\uff08\u3002\u3002\u6700\u5927\u6570\u636e\u8fd8\u8981\u9ad8\u7cbe\u5ea6\u5f00\u5e73\u65b9\u3002\u3002\uff09<\/p>\n\r\n... ..\r\nbignum l, r;\r\nLL res = 0;\r\n\r\nbignum sqrt(bignum x){\r\n bignum l = 0, r = x; while (l < r){\r\n bignum m = (l + r + 1) \/ 2;\r\n if (m*m<=x) l = m;\r\n else r = m - 1;\r\n }\r\n return l;\r\n}\r\n\r\nVS List;\r\n\r\nvoid gen(string c, int n){\r\n n *= 2; string cc = c; RVS(cc); List.PB(c+cc);\r\n REP(i, 3) if (n+i*i<=9) List.PB(c+char('0'+i)+cc);\r\n}\r\n\r\nvoid dfs(string c, int n){\r\n if (n > 4 || SZ(c) > 50) return; gen(c, n);\r\n REP(i, 3) dfs(c+char('0'+i), n+sqr(i));\r\n}\r\n\r\nbool cmp(const string &a, const string &b){\r\n return SZ(a) < SZ(b) || SZ(a) == SZ(b) && a < b;\r\n}\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n freopen("C-large-1.in", "r", stdin);\r\n freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n List.PB("1"); List.PB("2"); List.PB("3");\r\n dfs("1", 1); dfs("2", 4); SRT(List, cmp);\r\n\r\n \/\/REP(i, SZ(List)) cout << List[i] << endl;\r\n \/\/cout << SZ(List) <<endl;\r\n\r\n Rush{\r\n bignum ll, rr; cin >> ll >> rr; l = sqrt(ll), r = sqrt(rr);\r\n if (l*l < ll) l += 1;\r\n OT(upper_bound(ALL(List), r) - lower_bound(ALL(List), l));\r\n }\r\n}\r\n<\/pre>\nExternal link: <\/h3>\n","protected":false},"excerpt":{"rendered":"
Brief description: … \u95ee [L, R] \u533a\u95f4\u4e2d\u6709\u591a\u5c11 \u56de\u6587^2-\u6570\u3002\u3002 \u56de\u6587^2-\u6570\u3002\u3002\u6ee1\u8db3\u5176\u662f\u5b8c\u5168\u5e73\u65b9\u6570\u3002\u3002\u4e14\u5176\u672c\u8eab\u548c\u5e73\u65b9\u6839\u5747\u4e3a\u56de\u6587\u6570\u3002\u3002 (L, R<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-721","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-bD","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/721","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=721"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/721\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=721"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=721"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=721"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}