{"id":970,"date":"2014-09-17T22:15:05","date_gmt":"2014-09-17T14:15:05","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=970"},"modified":"2014-09-17T22:16:54","modified_gmt":"2014-09-17T14:16:54","slug":"srm-626","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/srm-626\/","title":{"rendered":"SRM 626"},"content":{"rendered":"

http:\/\/apps.topcoder.com\/wiki\/display\/tc\/SRM+626<\/p>\n

900. ReflectiveRectangle <\/h2>\n

Brief description: <\/h3>\n

\u3002\u7ed9\u5b9a\u4e00\u4e2a\u957f sideA \u5bbd sideB \u7684\u77e9\u9635\u3002\u3002
\n\u4ece\u5de6\u4e0b\u89d2\u53d1\u5c04\u4e00\u679a\u5149\u7ebf\uff0c\u8981\u6c42\u6070\u597d\u5728\u5899\u58c1\u53cd\u5c04 n \u6b21\u540e\u843d\u5165\u53f3\u4e0a\u89d2\uff0c\u4e14\u4e2d\u9014\u4e0d\u80fd\u7ecf\u8fc7 corner\u3002\u3002\u3002<\/p>\n

<\/p>\n

Analysis: <\/h3>\n

\u9996\u5148 n \u5fc5\u987b\u662f\u5076\u6570\u3002\u3002
\n\u8bbe\u5728\u6a2a\u8f74\u4e0e\u7eb5\u8f74\u5206\u522b\u53cd\u5f39 a, b \u6b21
\n\u90a3\u4e48\u5e73\u94fa\u540e\u7684\u957f\u5bbd\u5206\u522b\u4e3a (a+1)sideA, (b+1)sideB\u3002\u3002\u3002
\na+b == n\uff0cgcd(a+1, b+1) = 1
\n\u2014\u2014\u2014\u2014\u2014\u2014<\/p>\n

\u7136\u540e\u663e\u7136\u662f\u4e00\u4e2a\u83ab\u6bd4\u4e4c\u65af\u53cd\u6f14\u3002\u3002
\n\u3002\u3002\u3002<\/p>\n

\r\ns2(n) = 1^2 + 2^2 + \\ldots + n^2 = n*(n+1)*(2*n+1)\/6 ...\r\ng(d) = [d | gcd(i, n-i)] * (i^2)  =  sqr(d) * s2(n\/d);\r\nf(d) = [d = gcd(i, n-i)] * (i^2)\r\n...\r\n<\/pre>\n
\u5367\u69fd\u6211\u771f\u662f\u8822\u54ed\u4e86\u3002\u3002\u6211\u5c45\u7136\u5199\u6734\u7d20\u7684\u65f6\u5019\u6709\u4e00\u4e2a LL \u6ca1\u52a0\u3002\u3002\u4e00\u76f4\u6837\u4f8b\u6ca1\u51fa\u6765\u3002\u3002\u3002
\n\u3002\u3002\u3002\u8279\u3002\u77ac\u95f4\u6570\u8bba\u767d\u5b66\u4e86\u3002\u3002\uff08\u901f\u5ea6\u5199\u4e00\u4e2a\u6734\u7d20\u7684\u7b56\u7565\u672c\u8eab\u662f\u6ca1\u95ee\u9898\u7684\u3002\u3002\u3002\u4f46\u662f\u5904\u7406\u7684\u592a\u4e0d\u8c28\u614e\u4e86\u3002\u3002\uff09<\/p>\n
\r\nconst int PMAX = 46341;\r\n\r\nvector<int> P; bitset<PMAX> isC; int mu[PMAX];\r\n\r\nvoid sieve(){\r\n    mu[1] = 1; FOR(i, 2, PMAX){\r\n        if (!isC[i]) P.PB(i), mu[i] = -1;\r\n        for (int j=0;j<SZ(P)&&i*P[j]<PMAX;++j){\r\n            isC[i*P[j]]=1; if (!(i%P[j])){\r\n                mu[i*P[j]] = 0;\r\n                break;\r\n            } else{\r\n                mu[i*P[j]] = -mu[i];\r\n            }\r\n        }\r\n    }\r\n}\r\n\r\nVII fac; void fact(int x){\r\n    int z = x; fac.clear(); ECH(it, P) if (!(x%*it)){\r\n        int c=1; x\/=*it; while (!(x%*it)) x\/=*it, ++c;\r\n        fac.PB(MP(*it, c));\r\n    }\r\n    if (x!=1) fac.PB(MP(x, 1));\r\n}\r\n\r\nInt ans; int n;\r\n\r\nInt s2(Int n){\r\n    return n*(n+1)*(2*n+1)\/6;\r\n}\r\n\r\nInt f(Int d){\r\n    return s2(d)*sqr(Int(n\/d));\r\n}\r\n\r\nvoid gao(int k = 0, int c = 0, int d = 1){\r\n    if (k == SZ(fac)){\r\n        if (c&1) ans -= f(n\/d);\r\n        else ans += f(n\/d);\r\n    }\r\n    else{\r\n        gao(k+1, c, d);\r\n        gao(k+1, c+1, d*fac[k].fi);\r\n    }\r\n}\r\n\r\nclass ReflectiveRectangle {\r\npublic:\r\nint findSum(int sideA, int sideB, int n) {\r\n        if (n&1) return 0; Int cof = ((LL)sideA*sideA+(LL)sideB*sideB)%MOD;\r\n        ans = 0, n += 2, ::n = n;\r\n\r\n        REP_1(a, n){\r\n            int b = n-a; if (gcd(a, b) != 1) continue;\r\n            ans += sqr((Int)a);\r\n        }\r\n\r\n        \/\/cout << "b: " << n << endl;\r\n        \/\/sieve(); fact(n); gao();\r\n        return ans * cof;\r\n}\r\n};\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
http:\/\/apps.topcoder.com\/wiki\/display\/tc\/SRM+626 900. ReflectiveRectangle Brief description: \u3002\u7ed9\u5b9a\u4e00\u4e2a\u957f sideA \u5bbd sideB \u7684\u77e9\u9635\u3002\u3002 \u4ece\u5de6\u4e0b\u89d2\u53d1\u5c04\u4e00\u679a\u5149\u7ebf\uff0c\u8981\u6c42\u6070\u597d\u5728\u5899\u58c1\u53cd\u5c04 n \u6b21\u540e\u843d\u5165\u53f3\u4e0a\u89d2\uff0c\u4e14\u4e2d\u9014\u4e0d\u80fd\u7ecf\u8fc7 corner\u3002\u3002\u3002<\/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":[131],"class_list":["post-970","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-131"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-fE","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/970","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=970"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/970\/revisions"}],"predecessor-version":[{"id":971,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/970\/revisions\/971"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=970"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=970"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=970"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}