{"id":437,"date":"2023-01-17T23:58:25","date_gmt":"2023-01-17T15:58:25","guid":{"rendered":"https:\/\/blog.cirno.fun\/?p=437"},"modified":"2024-09-12T09:29:49","modified_gmt":"2024-09-12T01:29:49","slug":"acwing197-%e9%98%b6%e4%b9%98%e5%88%86%e8%a7%a3","status":"publish","type":"post","link":"https:\/\/blog.sssn.tech\/?p=437","title":{"rendered":"Acwing197.\u9636\u4e58\u5206\u89e3"},"content":{"rendered":"

\"file\"\u9636\u4e58\u5206\u89e3\u4e5f\u662f\u4e00\u9053\u975e\u5e38\u7ecf\u5178\u7684\u9898\u76ee\uff0c\u6d89\u53ca\u5230\u4e00\u4e2a\u91cd\u8981\u7ed3\u8bba<\/p>\n

\u5982\u679c\u6211\u4eec\u60f3\u5c06x!\u5206\u89e3\u8d28\u56e0\u6570\u4e3a<\/p>\n

x! = \\prod {p_i}^{\\alpha _i}<\/code><\/pre>\n
\u7684\u5f62\u5f0f\uff0c\u90a3\u4e48\u5bf9\u4e8e\u4efb\u610f\u4e00\u4e2a\u8d28\u56e0\u5b50p_i<\/code>\u7684\u6b21\u6570\\alpha _i<\/code>\uff0c\u6709<\/p>\n
\\alpha _i = \\sum_{i=1}^{\\infty } \\left \\lfloor \\frac{x}{p^i}  \\right \\rfloor <\/code><\/pre>\n
\u4e0d\u96be\u770b\u51fa\u548c\u5f0f\u5230\u67d0\u4e00\u9879\u4e4b\u540e\u56e0\u4e3a\u5206\u6bcd\u5927\u4e8e\u5206\u5b50\uff0c\u6240\u4ee5\u503c\u4e3a\u96f6\uff0c\u4e5f\u5c31\u662f\u8bf4\u5728\u7a0b\u5e8f\u4e2d\u6211\u4eec\u53ea\u9700\u505a\u5230\u5f53\u524d\u9879\u4e3a\u96f6\u5c31\u505c\u6b62\u7d2f\u52a0\u5373\u53ef<\/p>\n
\u8be5\u7ed3\u8bba\u7684\u4e00\u4e2a\u4e0d\u4e25\u8c28\u7406\u89e3\u65b9\u6cd5\u53ef\u4ee5\u7528Excel\u6765\u8868\u793a<\/p>\n
\"file\"<\/p>\n
\u8be5\u56fe\u7684\u57fa\u672c\u601d\u8def\u662f\uff0c\u5c0610!\u5206\u89e3\u6210109<\/em>87<\/em>65<\/em>43<\/em>2*1\u7684\u5f62\u5f0f\uff0c\u7136\u540e\u5728\u5176\u4e2d\u6311\u51fa2\u7684\u500d\u6570\u7684\u4e2a\u6570\uff08\u7b2c\u4e00\u5c42\uff09\uff0c\u7d2f\u52a0\uff0c\u518d\u6311\u51fa4\u7684\u500d\u6570\u7684\u4e2a\u6570\uff08\u7b2c\u4e8c\u5c42\uff09\uff0c\u7d2f\u52a0\uff0c\u7136\u540e\u4ee5\u6b64\u7c7b\u63a8\uff0c\u6bcf\u6b21\u7d2f\u52a0\u4e00\u5c42\u76f4\u81f3\u4e0d\u80fd\u4e3a\u6b62<\/p>\n
\u5982\u679c\u5199\u6210\u51fd\u6570\u7684\u5f62\u5f0f\u53ef\u4ee5\u8fd9\u6837<\/p>\n
int get_power(int x, int p)\n{\n    \/\/ \u8fd4\u56dex!\u4e2d\u8d28\u6570p\u4e3a\u56e0\u5b50\u7684\u6b21\u6570\n    \/\/ \u516c\u5f0f: \u6b21\u6570 = [x \/ p] + [x \/ p ^ 2] + [x \/ p ^ 3] + ^\n    int res = 0;\n    while(x)\n    {\n        res += x \/ p;\n        x \/= p;\n    }\n    return res;\n}<\/code><\/pre>\n
\u672c\u9898\u7684\u505a\u6cd5\u4fbf\u662f\u5148\u7528\u8d28\u6570\u7b5b\u5904\u7406\u51fa\u5c0f\u4e8en\u7684\u6240\u6709\u8d28\u6570\uff0c\u7136\u540e\u5bf9\u6bcf\u4e2a\u8d28\u6570p\u6c42\u51fa\u5728n!\u4e2dp\u4f5c\u4e3a\u8d28\u56e0\u5b50\u7684\u6307\u6570 \u5b8c\u6574\u4ee3\u7801<\/p>\n
#include <bits\/stdc++.h>\n\nusing namespace std;\ntypedef long long ll;\n\nconst int N = 1e6 + 10;\nint primes[N], idx[N]; \/\/ primes\u662f\u8d28\u6570\u8868\uff0cidx\u5b58\u5bf9\u5e94\u8d28\u6570\u8868\u7684\u6307\u6570\nbool v[N];\nint initPrimes(int n)\n{\n    \/\/ \u7ebf\u6027\u7b5b\uff08\u4e5f\u53eb\u6b27\u62c9\u7b5b\uff09\u6a21\u677f\uff0c\u5904\u7406\u51fan\u4ee5\u5185\u7684\u8d28\u6570\u5e76\u4e14\u8fd4\u56de\u4e2a\u6570\n    int cnt = 0;\n    for(int i = 2; i <= n; i++)\n    {\n        if(!v[i])   primes[++cnt] = i;\n        for(int j = 1; primes[j] <= n \/ i; j++)\n        {\n            v[primes[j] * i] = true;\n            if(i % primes[j] == 0)  break;\n        }\n    }\n    return cnt;\n}\n\nint main()\n{\n    int n;\n    scanf("%d", &n);\n\n    int cnt = initPrimes(n);\n\n    for(int i = 1; i <= cnt; i++)\n    {\n        int p = primes[i];\n        int tempN = n, pw = 0;\n        while(tempN)\n        {\n            pw += tempN \/ p;\n            tempN \/= p;\n        }\n        if(pw)\n        {\n            printf("%d %d\\n", p, pw);\n        }\n    }\n\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9636\u4e58\u5206\u89e3\u4e5f\u662f\u4e00\u9053\u975e\u5e38\u7ecf\u5178\u7684\u9898\u76ee\uff0c\u6d89\u53ca\u5230\u4e00\u4e2a\u91cd\u8981\u7ed3\u8bba \u5982\u679c\u6211\u4eec\u60f3\u5c06x!\u5206\u89e3\u8d28\u56e0\u6570\u4e3a […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[16,23],"tags":[],"class_list":["post-437","post","type-post","status-publish","format-standard","hentry","category-16","category-23"],"_links":{"self":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/437","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=437"}],"version-history":[{"count":1,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/437\/revisions"}],"predecessor-version":[{"id":730,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/437\/revisions\/730"}],"wp:attachment":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=437"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=437"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=437"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}