{"id":235,"date":"2010-04-27T17:05:00","date_gmt":"2010-04-27T09:05:00","guid":{"rendered":"http:\/\/localhost\/?p=235"},"modified":"2023-01-30T19:45:24","modified_gmt":"2023-01-30T19:45:24","slug":"370","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=235","title":{"rendered":"SGU 370"},"content":{"rendered":"\n<p>\u9898\u76ee\u5728<a href=\"http:\/\/acm.sgu.ru\/problem.php?contest=0&amp;problem=370\">http:\/\/acm.sgu.ru\/problem.php?contest=0&amp;problem=370<\/a><br \/>\u9996\u5148\u7279\u5224\u6389n=1\u6216m=1\u6216n\u3001m\u90fd\u7b49\u4e8e1\u7684\u60c5\u51b5\u3002\u3002<br \/>\u7136\u540e\u7b54\u6848\u5c31\u662fp&lt;=n&amp;&amp;p&lt;=m&amp;&amp;(p,q)=1\u7684\u6570\u5bf9\u7684\u4e2a\u6570\u3002\u3002<br \/>\u5f88\u660e\u663e\u53ef\u4ee5\u7528\u5bb9\u65a5\u539f\u7406\u505a\u3002\u3002<br \/>\u5c31OK\u4e86\u3002\u3002<\/p>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\r\n#include&lt;iostream&gt;\r\n#include&lt;vector&gt;\r\n#include&lt;algorithm&gt;\r\n#include&lt;cstring&gt;\r\nusing namespace std;\r\nconst int maxn=1000000+1;\r\nint n,m,pnt,*P;\r\nlong long ans=0;\r\nint S[maxn][10],D[maxn]= {};\r\nvoid dfs(int p,int ch,int now)\r\n{\r\n    if(now&gt;n)return;\r\n    if(p==pnt)\r\n    {\r\n        if(ch&amp;1)ans-=n\/now;\r\n        else ans+=n\/now;\r\n        return;\r\n    }\r\n    dfs(p+1,ch,now);\r\n    dfs(p+1,ch+1,now*P[p]);\r\n}\r\n\r\nint main()\r\n{\r\n    \/\/freopen(&quot;in&quot;,&quot;r&quot;,stdin);\r\n    cin&gt;&gt;n&gt;&gt;m;\r\n    n--;\r\n    m--;\r\n    if(m&gt;n)swap(n,m);\r\n    if(!n)\r\n    {\r\n        cout&lt;&lt;0&lt;&lt;endl;\r\n        return 0;\r\n    }\r\n    if(!m)\r\n    {\r\n        cout&lt;&lt;1&lt;&lt;endl;\r\n        return 0;\r\n    }\r\n    for(int i=1; i&lt;=m; i++)\r\n    {\r\n        if(i==1)\r\n        {\r\n            ans+=n;\r\n            continue;\r\n        }\r\n        int t=i,a;\r\n        P=S[i];\r\n        for(a=2; a*a&lt;=t; a++) if(t%a==0)\r\n            {\r\n                while(t%a==0)\r\n                {\r\n                    t\/=a;\r\n                }\r\n                break;\r\n            }\r\n        if(t==i)P[D[i]++]=t;\r\n        else\r\n        {\r\n            D[i]=D[t]+1;\r\n            memcpy(P,S[t],sizeof(S[t]));\r\n            P[D[i]-1]=a;\r\n        }\r\n        pnt=D[i];\r\n        dfs(0,0,1);\r\n    }\r\n    cout&lt;&lt;ans+2&lt;&lt;endl;\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u5728http:\/\/acm.sgu.ru\/problem.php?contest=0&amp;problem=370\u9996\u5148\u7279\u5224\u6389n=1\u6216m=1\u6216n\u3001m\u90fd\u7b49\u4e8e1\u7684\u60c5\u51b5\u3002\u3002\u7136\u540e\u7b54\u6848\u5c31\u662fp&lt;=n&amp;&amp;p&lt;=m&amp;&amp;(p,q)=1\u7684\u6570\u5bf9\u7684\u4e2a\u6570\u3002\u3002\u5f88\u660e\u663e\u53ef\u4ee5\u7528\u5bb9\u65a5\u539f\u7406\u505a\u3002\u3002\u5c31OK\u4e86\u3002\u3002<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/235"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=235"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/235\/revisions"}],"predecessor-version":[{"id":772,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/235\/revisions\/772"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=235"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=235"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=235"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}