{"id":40,"date":"2022-06-04T10:52:00","date_gmt":"2022-06-04T02:52:00","guid":{"rendered":"http:\/\/ubuntu.tim-wcx.ltd\/wordpress\/index.php\/2022\/06\/04\/2020-08-05\/"},"modified":"2022-06-04T10:52:00","modified_gmt":"2022-06-04T02:52:00","slug":"2020-08-05","status":"publish","type":"post","link":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/2022\/06\/04\/2020-08-05\/","title":{"rendered":"2020-08-05"},"content":{"rendered":"

\n <\/path>\n <\/svg><\/p>\n

http:\/\/icpc.upc.edu.cn\/problem.php?cid=1442&pid=0<\/a><\/p>\n

<\/a>\u9898\u76ee\u63cf\u8ff0<\/h5>\n

\u7ed9\u5b9a\u6574\u6570N(1\u2264N\u226410^6)\uff0c\u8bd5\u628a\u9636\u4e58N!\u5206\u89e3\u8d28\u56e0\u6570\uff0c\u6309\u7167\u7b97\u672f\u57fa\u672c\u5b9a\u7406\u7684\u5f62\u5f0f\u8f93\u51fa\u5206\u89e3\u7ed3\u679c\u4e2d\u7684pi\u548cci\u5373\u53ef\u3002<\/p>\n

<\/a>\u8f93\u5165<\/h5>\n

\u4e00\u4e2a\u6574\u6570N\u3002<\/p>\n

<\/a>\u8f93\u51fa<\/h5>\n

N! \u5206\u89e3\u8d28\u56e0\u6570\u540e\u7684\u7ed3\u679c\uff0c\u5171\u82e5\u5e72\u884c\uff0c\u6bcf\u884c\u4e00\u5bf9pi, ci\uff0c\u8868\u793a\u542b\u6709pi^ci\u9879\u3002\u6309\u7167pi\u4ece\u5c0f\u5230\u5927\u7684\u987a\u5e8f\u8f93\u51fa\u3002<\/p>\n

<\/a>\u6837\u4f8b\u8f93\u5165<\/h5>\n
5\n<\/code><\/pre>\n
<\/a>\u6837\u4f8b\u8f93\u51fa<\/h5>\n
2 3\n3 1\n5 1\n<\/code><\/pre>\n
<\/a>\u63d0\u793a<\/h5>\n
5! = 120 = 2^3 * 3 * 5<\/p>\n
<\/a>\u89e3\u6790\uff1a<\/h5>\n
\u6b27\u62c9\u7b5b\u6cd5
 https:\/\/blog.csdn.net\/WHZ2018\/article\/details\/81233937<\/a><\/p>\n
#pragma<\/span> GCC optimize(1)<\/span>\n#pragma<\/span> GCC optimize(2)<\/span>\n#pragma<\/span> GCC optimize(3,\"Ofast\",\"inline\")<\/span>\n#include<\/span> <\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\ntypedef<\/span> long<\/span> long<\/span> ll;<\/span>\nint<\/span> pd[<\/span>1005000<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nll c[<\/span>1005000<\/span>]<\/span>=<\/span>{<\/span>0<\/span>}<\/span>;<\/span>\nll n,<\/span>k;<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    ll cnt=<\/span>0<\/span>;<\/span>\n    scanf<\/span>(<\/span>\"%lld\"<\/span>,<\/span>&<\/span>n)<\/span>;<\/span>\n    pd[<\/span>0<\/span>]<\/span>=<\/span>pd[<\/span>1<\/span>]<\/span>=<\/span>1<\/span>;<\/span>\n    for<\/span>(<\/span>ll i=<\/span>2<\/span>;<\/span>i<=<\/span>n;<\/span>i++<\/span>)<\/span>\n    {<\/span>\n        if<\/span>(<\/span>!<\/span>pd[<\/span>i]<\/span>)<\/span>\n            c[<\/span>cnt++<\/span>]<\/span>=<\/span>i;<\/span>\n        for<\/span>(<\/span>ll j=<\/span>0<\/span>;<\/span>j<<\/span>cnt&&<\/span>c[<\/span>j]<\/span>*<\/span>i<=<\/span>n;<\/span>j++<\/span>)<\/span>\n        {<\/span>\n            pd[<\/span>c[<\/span>j]<\/span>*<\/span>i]<\/span>=<\/span>1<\/span>;<\/span>\n            if<\/span>(<\/span>i%<\/span>c[<\/span>j]<\/span>==<\/span>0<\/span>)<\/span>\n                break<\/span>;<\/span>\n        }<\/span>\n    }<\/span>\n    for<\/span>(<\/span>ll i=<\/span>0<\/span>;<\/span>i<<\/span>cnt;<\/span>i++<\/span>)<\/span>\n    {<\/span>\n        ll sum=<\/span>0<\/span>;<\/span>\n        for<\/span>(<\/span>ll j=<\/span>c[<\/span>i]<\/span>;<\/span>j<=<\/span>n;<\/span>j=<\/span>j*<\/span>c[<\/span>i]<\/span>)<\/span>\n            sum+<\/span>=<\/span>n\/<\/span>j;<\/span>\n        printf<\/span>(<\/span>\"%lld %lldn\"<\/span>,<\/span>c[<\/span>i]<\/span>,<\/span>sum)<\/span>;<\/span>\n    }<\/span>\n    return<\/span> 0<\/span>;<\/span>\n}<\/span>\n\n<\/code><\/pre>\n
\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"
 \u4efb\u4e00\u5927\u4e8e2\u7684\u5076\u6570\u90fd\u53ef\u5199\u6210\u4e24\u4e2a\u8d28\u6570\u4e4b\u548c\uff0c\u5206\u5947\u5076\u8ba8\u8bba\u5373\u53ef\u3002<\/p>\n
#include<\/span> <\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\ntypedef<\/span> long<\/span> long<\/span> ll;<\/span>\nll gcd<\/span>(<\/span>ll a,<\/span>ll b)<\/span>\n{<\/span>\n    if<\/span>(<\/span>b==<\/span>0<\/span>)<\/span>\n        return<\/span> a;<\/span>\n    else<\/span>\n        return<\/span> gcd<\/span>(<\/span>b,<\/span>a%<\/span>b)<\/span>;<\/span>\n}<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    int<\/span> t;<\/span>\n    scanf<\/span>(<\/span>\"%d\"<\/span>,<\/span>&<\/span>t)<\/span>;<\/span>\n    while<\/span>(<\/span>t--<\/span>)<\/span>\n    {<\/span>\n        ll n,<\/span>k;<\/span>\n        scanf<\/span>(<\/span>\"%lld%lld\"<\/span>,<\/span>&<\/span>n,<\/span>&<\/span>k)<\/span>;<\/span>\n        if<\/span>(<\/span>n%<\/span>k!=<\/span>0<\/span>)<\/span>\n        {<\/span>\n            puts<\/span>(<\/span>\"-1 -1 -1\"<\/span>)<\/span>;<\/span>continue<\/span>;<\/span>\n        }<\/span>\n        ll w=<\/span>n\/<\/span>k,<\/span>a,<\/span>b,<\/span>c;<\/span>\n        int<\/span> flag=<\/span>1<\/span>;<\/span>\n        if<\/span>(<\/span>w%<\/span>2<\/span>==<\/span>1<\/span>)<\/span>\n        {<\/span>\n            a=<\/span>3<\/span>,<\/span>b=<\/span>2<\/span>,<\/span>c=<\/span>w-<\/span>a-<\/span>b;<\/span>\n            while<\/span>(<\/span>c><\/span>2<\/span>)<\/span>\n            {<\/span>\n                if<\/span>(<\/span>gcd<\/span>(<\/span>a,<\/span>b)<\/span>==<\/span>1<\/span>&&<\/span>gcd<\/span>(<\/span>b,<\/span>c)<\/span>==<\/span>1<\/span>&&<\/span>gcd<\/span>(<\/span>a,<\/span>c)<\/span>==<\/span>1<\/span>)<\/span>\n                {<\/span>\n                    flag=<\/span>0<\/span>;<\/span>\n                    break<\/span>;<\/span>\n                }<\/span>\n                b++<\/span>;<\/span>c--<\/span>;<\/span>\n            }<\/span>\n        }<\/span>\n        else<\/span>\n        {<\/span>\n            a=<\/span>2<\/span>,<\/span>b=<\/span>2<\/span>,<\/span>c=<\/span>w-<\/span>a-<\/span>b;<\/span>\n            while<\/span>(<\/span>c><\/span>2<\/span>)<\/span>\n            {<\/span>\n                if<\/span>(<\/span>gcd<\/span>(<\/span>a,<\/span>b)<\/span>==<\/span>1<\/span>&&<\/span>gcd<\/span>(<\/span>b,<\/span>c)<\/span>==<\/span>1<\/span>&&<\/span>gcd<\/span>(<\/span>a,<\/span>c)<\/span>==<\/span>1<\/span>)<\/span>\n                {<\/span>\n                    flag=<\/span>0<\/span>;<\/span>\n                    break<\/span>;<\/span>\n                }<\/span>\n                b++<\/span>;<\/span>c--<\/span>;<\/span>\n            }<\/span>\n        }<\/span>\n        if<\/span>(<\/span>flag)<\/span>\n            puts<\/span>(<\/span>\"-1 -1 -1\"<\/span>)<\/span>;<\/span>\n        else<\/span>\n            printf<\/span>(<\/span>\"%lld %lld %lldn\"<\/span>,<\/span>a*<\/span>k,<\/span>b*<\/span>k,<\/span>c*<\/span>k)<\/span>;<\/span>\n    }<\/span>\n    return<\/span> 0<\/span>;<\/span>\n}<\/span>\n\n<\/code><\/pre>\n
<\/a>\u4ee3\u7801<\/h5>\n
\u65b9\u6cd51\uff1a<\/p>\n
#include<\/span> <\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\ntypedef<\/span> long<\/span> long<\/span> ll;<\/span>\nmap<<\/span>ll,<\/span>ll><\/span>w;<\/span>\nchar<\/span> a[<\/span>2000<\/span>]<\/span>=<\/span> {<\/span>0<\/span>}<\/span>;<\/span>\nll b[<\/span>3000<\/span>]<\/span>=<\/span> {<\/span>0<\/span>}<\/span>;<\/span>\nll two<\/span>(<\/span>)<\/span>\n{<\/span>\n    for<\/span>(<\/span>ll i=<\/span>1<\/span>;<\/span> i<=<\/span>8<\/span>;<\/span> i++<\/span>)<\/span>\n    {<\/span>\n        ll w1;<\/span>\n        if<\/span>(<\/span>a[<\/span>i]<\/span>>=<\/span>'0'<\/span>&&<\/span>a[<\/span>i]<\/span><=<\/span>'9'<\/span>)<\/span>\n        {<\/span>\n            w1=<\/span>a[<\/span>i]<\/span>-<\/span>'0'<\/span>;<\/span>\n        }<\/span>\n        else<\/span> if<\/span>(<\/span>a[<\/span>i]<\/span>==<\/span>'A'<\/span>)<\/span>\n        {<\/span>\n            w1=<\/span>10<\/span>;<\/span>\n        }<\/span>\n        else<\/span> if<\/span>(<\/span>a[<\/span>i]<\/span>==<\/span>'B'<\/span>)<\/span>\n        {<\/span>\n            w1=<\/span>11<\/span>;<\/span>\n        }<\/span>\n        else<\/span> if<\/span>(<\/span>a[<\/span>i]<\/span>==<\/span>'C'<\/span>)<\/span>\n        {<\/span>\n            w1=<\/span>12<\/span>;<\/span>\n        }<\/span>\n        else<\/span> if<\/span>(<\/span>a[<\/span>i]<\/span>==<\/span>'D'<\/span>)<\/span>\n        {<\/span>\n            w1=<\/span>13<\/span>;<\/span>\n        }<\/span>\n        else<\/span> if<\/span>(<\/span>a[<\/span>i]<\/span>==<\/span>'E'<\/span>)<\/span>\n        {<\/span>\n            w1=<\/span>14<\/span>;<\/span>\n        }<\/span>\n        else<\/span> if<\/span>(<\/span>a[<\/span>i]<\/span>==<\/span>'F'<\/span>)<\/span>\n        {<\/span>\n            w1=<\/span>15<\/span>;<\/span>\n        }<\/span>\n        for<\/span>(<\/span>ll j=<\/span>i*<\/span>4<\/span>;<\/span> j><\/span>(<\/span>i-<\/span>1<\/span>)<\/span>*<\/span>4<\/span>;<\/span> j--<\/span>)<\/span>\n        {<\/span>\n            b[<\/span>j]<\/span>=<\/span>w1%<\/span>2<\/span>;<\/span>\n            w1=<\/span>w1\/<\/span>2<\/span>;<\/span>\n        }<\/span>\n    }<\/span>\n}<\/span>\nll six<\/span>(<\/span>)<\/span>\n{<\/span>\n    ll sum=<\/span>0<\/span>;<\/span>\n    for<\/span>(<\/span>ll i=<\/span>1<\/span>;<\/span> i<=<\/span>8<\/span>;<\/span> i++<\/span>)<\/span>\n    {<\/span>\n        sum=<\/span>0<\/span>;<\/span>\n        for<\/span>(<\/span>ll j=<\/span>4<\/span>*<\/span>(<\/span>i-<\/span>1<\/span>)<\/span>+<\/span>1<\/span>;<\/span>j<=<\/span>4<\/span>*<\/span>i;<\/span>j++<\/span>)<\/span>\n            sum=<\/span>sum*<\/span>2<\/span>+<\/span>b[<\/span>j]<\/span>;<\/span>\n        if<\/span>(<\/span>sum<=<\/span>9<\/span>&&<\/span>sum>=<\/span>0<\/span>)<\/span>\n            printf<\/span>(<\/span>\"%d\"<\/span>,<\/span>sum)<\/span>;<\/span>\n        else<\/span> if<\/span>(<\/span>sum==<\/span>10<\/span>)<\/span>\n            printf<\/span>(<\/span>\"A\"<\/span>)<\/span>;<\/span>\n        else<\/span> if<\/span>(<\/span>sum==<\/span>11<\/span>)<\/span>\n            printf<\/span>(<\/span>\"B\"<\/span>)<\/span>;<\/span>\n        else<\/span> if<\/span>(<\/span>sum==<\/span>12<\/span>)<\/span>\n            printf<\/span>(<\/span>\"C\"<\/span>)<\/span>;<\/span>\n        else<\/span> if<\/span>(<\/span>sum==<\/span>13<\/span>)<\/span>\n            printf<\/span>(<\/span>\"D\"<\/span>)<\/span>;<\/span>\n        else<\/span> if<\/span>(<\/span>sum==<\/span>14<\/span>)<\/span>\n            printf<\/span>(<\/span>\"E\"<\/span>)<\/span>;<\/span>\n        else<\/span> if<\/span>(<\/span>sum==<\/span>15<\/span>)<\/span>\n            printf<\/span>(<\/span>\"F\"<\/span>)<\/span>;<\/span>\n    }<\/span>\n    printf<\/span>(<\/span>\"n\"<\/span>)<\/span>;<\/span>\n}<\/span>\nll n,<\/span>m,<\/span>p,<\/span>k,<\/span>summ=<\/span>1<\/span>,<\/span>q,<\/span>sum1,<\/span>o;<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n    scanf<\/span>(<\/span>\"%lld%lld%lld\"<\/span>,<\/span>&<\/span>n,<\/span>&<\/span>m,<\/span>&<\/span>p)<\/span>;<\/span>\n    for<\/span>(<\/span>ll i=<\/span>0<\/span>;<\/span> i<<\/span>(<\/span>1<\/span><<<\/span>(<\/span>m-<\/span>p)<\/span>)<\/span>;<\/span> i++<\/span>)<\/span>\n    {<\/span>\n        scanf<\/span>(<\/span>\"%lld\"<\/span>,<\/span>&<\/span>k)<\/span>;<\/span>\n        w[<\/span>k]<\/span>=<\/span>i;<\/span>\n    }<\/span>\n    scanf<\/span>(<\/span>\"%lld\"<\/span>,<\/span>&<\/span>q)<\/span>;<\/span>\n    for<\/span>(<\/span>ll i=<\/span>1<\/span>;<\/span> i<=<\/span>q;<\/span> i++<\/span>)<\/span>\n    {<\/span>\n        scanf<\/span>(<\/span>\"%s\"<\/span>,<\/span>a+<\/span>1<\/span>)<\/span>;<\/span>\n        two<\/span>(<\/span>)<\/span>;<\/span>\n        sum1=<\/span>0<\/span>;<\/span>\n        for<\/span>(<\/span>ll i=<\/span>1<\/span>;<\/span> i<=<\/span>32<\/span>-<\/span>p;<\/span> i++<\/span>)<\/span>\n            sum1=<\/span>sum1*<\/span>2<\/span>+<\/span>b[<\/span>i]<\/span>;<\/span>\n        if<\/span>(<\/span>w.<\/span>find<\/span>(<\/span>sum1)<\/span>==<\/span>w.<\/span>end<\/span>(<\/span>)<\/span>)<\/span>\n        {<\/span>\n            puts<\/span>(<\/span>\"interrupt!\"<\/span>)<\/span>;<\/span>\n        }<\/span>\n        else<\/span>\n        {<\/span>\n            o=<\/span>w[<\/span>sum1]<\/span>;<\/span>\n            for<\/span>(<\/span>ll i=<\/span>32<\/span>-<\/span>p;<\/span> i>=<\/span>1<\/span>;<\/span> i--<\/span>)<\/span>\n            {<\/span>\n                b[<\/span>i]<\/span>=<\/span>o%<\/span>2<\/span>;<\/span>\n                o=<\/span>o\/<\/span>2<\/span>;<\/span>\n            }<\/span>\n            six<\/span>(<\/span>)<\/span>;<\/span>\n        }<\/span>\n    }<\/span>\n    return<\/span> 0<\/span>;<\/span>\n}<\/span>\n\n<\/code><\/pre>\n
\u65b9\u6cd52\uff1a<\/p>\n
#include<\/span> <\/span><\/span>\nusing<\/span> namespace<\/span> std;<\/span>\ntypedef<\/span> long<\/span> long<\/span> ll;<\/span>\nmap<<\/span>ll,<\/span>ll><\/span>w;<\/span>\nint<\/span> main<\/span>(<\/span>)<\/span>\n{<\/span>\n\tll n,<\/span>m,<\/span>p;<\/span>\n\tscanf<\/span>(<\/span>\"%lld%lld%lld\"<\/span>,<\/span>&<\/span>n,<\/span>&<\/span>m,<\/span>&<\/span>p)<\/span>;<\/span>\n\tfor<\/span> (<\/span>ll i=<\/span>0<\/span>;<\/span>i<<\/span>1<\/span><<<\/span>(<\/span>m-<\/span>p)<\/span>;<\/span>i++<\/span>)<\/span>\n\t{<\/span>\n\t\tll pos;<\/span>\n\t\tscanf<\/span>(<\/span>\"%lld\"<\/span>,<\/span>&<\/span>pos)<\/span>;<\/span>\n\t\tw[<\/span>pos]<\/span>=<\/span>i;<\/span>\n\t}<\/span>\n\tll q;<\/span>\n\tscanf<\/span>(<\/span>\"%lld\"<\/span>,<\/span>&<\/span>q)<\/span>;<\/span>\n\twhile<\/span>(<\/span>q--<\/span>)<\/span>\n\t{<\/span>\n\t\tll tmp;<\/span>\n\t\tscanf<\/span>(<\/span>\"%llX\"<\/span>,<\/span>&<\/span>tmp)<\/span>;<\/span>\n\t\tprintf<\/span>(<\/span>\"%lldn\"<\/span>,<\/span>tmp)<\/span>;<\/span>\n\t\tll t1=<\/span>tmp\/<\/span>(<\/span>1<\/span><<<\/span>p)<\/span>,<\/span>t2=<\/span>tmp%<\/span>(<\/span>1<\/span><<<\/span>p)<\/span>;<\/span>\n\t\tif<\/span> (<\/span>w.<\/span>find<\/span>(<\/span>t1)<\/span>==<\/span>w.<\/span>end<\/span>(<\/span>)<\/span>)<\/span>\n\t\t{<\/span>\n\t\t\tprintf<\/span>(<\/span>\"interrupt!n\"<\/span>)<\/span>;<\/span>\n\t\t}<\/span>\n\t\telse<\/span>\n\t\t{<\/span>\n\t\t\tprintf<\/span>(<\/span>\"%08llXn\"<\/span>,<\/span>w[<\/span>t1]<\/span>*<\/span>(<\/span>1<\/span><<<\/span>p)<\/span>+<\/span>t2)<\/span>;<\/span>\n\t\t}<\/span>\n\t}<\/span>\n    return<\/span> 0<\/span>;<\/span>\n}<\/span>\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
http:\/\/icpc.upc.edu.cn\/pr…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-40","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/40","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/comments?post=40"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/40\/revisions"}],"wp:attachment":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/media?parent=40"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/categories?post=40"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/tags?post=40"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
<\/a>\u9898\u76ee<\/h6>\n
https:\/\/ac.nowcoder.com\/acm\/contest\/6871\/E<\/a><\/p>\n