<\/p>\n\n\n\n
Polya\u5b9a\u7406\u662f\u4e00\u4e2a\u5173\u4e8e\u7f6e\u6362\u7fa4\u4e2d\u7ec4\u5408\u8ba1\u6570\u7684\u5b9a\u7406\u3002
\n\u9996\u5148\u6211\u4eec\u6765\u4e86\u89e3Burnside\u5f15\u7406\u3002\u8fd9\u4e2a\u5f15\u7406\u7684\u8bc1\u660e\u8f83\u4e3a\u590d\u6742\uff0c\u5728\u8fd9\u91cc\u4ec5\u4ecb\u7ecd\u5176\u5185\u5bb9\u3002
\nBurnside\u5f15\u7406\u7684\u5185\u5bb9\u662f\u8fd9\u6837\u7684\uff1a\u5728\u7f6e\u6362\u610f\u4e49\u4e0b\u672c\u8d28\u4e0d\u540c\u7684\u67d3\u8272\u65b9\u6848\u6570\uff0c\u7b49\u4e8e\u5355\u4e2a\u7f6e\u6362\u4e0d\u4f1a\u6539\u53d8\u7684\u67d3\u8272\u65b9\u6848\u6570\u7684\u5e73\u5747\u503c\u3002
\n\u90a3\u4e48\uff0c\u5355\u4e2a\u7f6e\u6362\u4e0d\u4f1a\u6539\u53d8\u7684\u67d3\u8272\u65b9\u6848\u6570\u8981\u600e\u4e48\u6c42\u5462\uff1f\u6211\u4eec\u4e0d\u59a8\u628a\u7f6e\u6362\u5173\u7cfb\u5efa\u6210\u4e00\u5f20\u56fe\uff0c\u90a3\u4e48\u8fd9\u5f20\u56fe\u5fc5\u7136\u7531\u82e5\u5e72\u4e2a\u73af\u6784\u6210\u3002\u4e5f\u5c31\u662f\u8bf4\uff0c\u5bf9\u4e8e\u540c\u4e00\u79cd\u7f6e\u6362\uff0c\u53ef\u80fd\u5b58\u5728\u82e5\u5e72\u4e2a\u73af\uff0c\u800c\u6bcf\u4e2a\u521d\u59cb\u72b6\u6001\u5c31\u662f\u73af\u4e0a\u7684\u4e00\u4e2a\u8282\u70b9\u3002Polya\u5b9a\u7406\u63cf\u8ff0\u7684\u5c31\u662f\uff0c\u67d0\u4e00\u79cd\u7f6e\u6362\u4e0d\u4f1a\u6539\u53d8\u7684\u65b9\u6848\u6570\uff0c\u7b49\u4e8e\u989c\u8272\u6570\u7684\u300c\u8fd9\u4e2a\u7f6e\u6362\u5bf9\u5e94\u7684\u5faa\u73af\u8282\u4e2a\u6570\u300d<\/p>\n\n\n\n
\u9610\u8ff0\u4e86\u4e0a\u8ff0\u4e24\u4e2a\u5b9a\u7406\uff0c\u73b0\u5728\u6211\u4eec\u6765\u770b\u8fd9\u4e00\u9898\u3002
\n\u6211\u4eec\u89c2\u5bdf\u5230\uff0c\u8fd9\u4e2a\u73af\u4e0a\u5b58\u5728 n \u79cd\u7f6e\u6362\u3002\u5bf9\u4e8e\u7f6e\u6362 i \u800c\u8a00\uff0c\u5b83\u7684\u5faa\u73af\u5927\u5c0f\u662f\uff1a
\n$$
\n\\frac{n}{\\gcd(n,i)}
\n$$
\n\u8fd9\u4e5f\u5c31\u610f\u5473\u7740\uff0c\u5b83\u7684\u5faa\u73af\u4e2a\u6570\u662f\uff1a
\n$$
\n\\gcd(n,i)
\n$$
\n\u90a3\u4e48\u6211\u4eec\u8981\u6c42\u7684\u7b54\u6848\u5c31\u662f\uff1a
\n$$
\n\\frac{\\sum_{i=1}^nn^{(n,i)}}{n}
\n$$
\n\u7136\u800c\u8fd9\u6837\u8ba1\u7b97\u7b54\u6848\u7684\u590d\u6742\u5ea6\u662f O(n) \u7684\uff0c\u6211\u4eec\u65e0\u6cd5\u63a5\u53d7\u3002
\n\u6211\u4eec\u4e0d\u59a8\u8003\u8651\u679a\u4e3e\u8fd9\u4e2a\u516c\u56e0\u5b50\u3002\u90a3\u4e48\uff0c\u5bb9\u6613\u8bc1\u660e\u7684\u662f\uff0c\u6bcf\u4e00\u4e2a\u516c\u56e0\u5b50d\u5bf9\u5e94\u7684\u7f6e\u6362\u4e2a\u6570\u662f\\(\\varphi(\\frac{n}{d})\\)<\/p>\n\n\n\n
\u8fd9\u662f\u56e0\u4e3a\uff0c d \u662f \\(\\frac{n}{d}\\) \u4e2a\u6570\u7684\u56e0\u6570\uff0c\u800c\u8fd9\u4e9b\u6570\u4e2d\uff0c\u5982\u679c\u5b83\u548c\\(\\frac{n}{d}\\)\u5b58\u5728\u516c\u56e0\u5b50\u7684\u8bdd\uff0c\u90a3\u4e48\u5b83\u548cn\u7684\u6700\u5927\u516c\u56e0\u6570\u5fc5\u7136\u5927\u4e8ed\u3002<\/p>\n\n\n\n
\u6240\u4ee5\uff0c\u6211\u4eec\u6c42\u7684\u5c31\u662f\uff1a
\n$$
\n\\frac{\\sum_{d|n}\\varphi(\\frac{n}{d})n^{\\frac{n}{d}}}{n}=\\sum_{d|n}\\varphi(\\frac{n}{d})n^{\\frac{n}{d}-1}
\n$$
\n\u6211\u4eec\u53ea\u8981\u679a\u4e3en\u7684\u56e0\u6570\u5373\u53ef\u3002<\/p>\n\n\n\n
\u7136\u800c\u6c42\u8fd9\u91cc\u7684 \\(\\varphi\\) \u5012\u53ef\u80fd\u5b58\u5728\u4e00\u4e9b\u95ee\u9898\u3002\u4e8b\u5b9e\u4e0a\uff0c\u7531\u4e8e\u6211\u4eec\u8981\u53d6\u7684\u56e0\u6570\u7684\u503c\u57df\u662f \\(10^9\\) \uff0c\u6211\u4eec\u65e0\u6cd5\u4f7f\u7528\u6b27\u62c9\u7b5b\u6765\u9884\u5904\u7406\uff0c\u800c\u9700\u8981\u73b0\u573a\u505a\u3002<\/p>\n\n\n\n
\u8fd9\u6837\u7684\u590d\u6742\u5ea6\u662f\u4e0d\u662f\u5bf9\u7684\u5462\uff1f\u5b83\u7684\u6700\u574f\u60c5\u51b5\u662f \\(O(Tn^{\\frac{3}{4}})\\) \u7684\uff0c\u4f46\u7531\u4e8e\u6211\u5e76\u4e0d\u4f1a\u5206\u6790\u7684\u4e00\u4e9b\u6027\u8d28\uff0c\u5b83\u4e0d\u4f1a\u8fbe\u5230\u8fd9\u4e2a\u503c\u3002\u56e0\u6b64\u53ef\u4ee5\u901a\u8fc7\u6b64\u9898\u3002 <\/p>\n\n\n\n
\u53e6\uff1a\u62ec\u53f7\u5fd8\u8bb0\u52a0\uff0c\u7206O\u6cea\u4e24\u884c\u3002<\/p>\n\n\n\n
#include<iostream>\n#include<cstdio>\n#include<cstring>\n#include<algorithm>\n#include<queue>\n#include<vector>\nusing namespace std;\ntypedef long long ll;\nconst ll MOD=1000000007;\nconst int N=1000005;\ninline ll pw(ll A,ll X){\n\tll RT=1;\n\twhile(X){\n\t\tif(X&1){\n\t\t\tRT*=A;RT%=MOD;\n\t\t}\n\t\tA*=A;A%=MOD,X>>=1;\n\t}\n\treturn RT;\n}\nint n;\ninline int phi(int X){\n\tint RT=1;\n\tfor(int i=2;i*i<=X;++i){\n\t\tif(X%i==0){\n\t\t\tX\/=i;RT*=i-1;\n\t\t\twhile(X%i==0){\n\t\t\t\tX\/=i;RT*=i;\n\t\t\t}\n\t\t}\n\t\tif(X==1){\n\t\t\tbreak;\n\t\t} \n\t}\n\tif(X>1){\n\t\tRT*=X-1;\n\t}\n\treturn RT;\n}\nvoid init(){\n\tscanf(\"%d\",&n);\n\tll ans=0;\n\tfor(int i=1;i*i<=n;++i){\n\t\tif(n%i==0){\n\t\t\tans+=(1ll*phi(n\/i)*pw(n,i-1))%MOD;\n\t\t\tif(i*i!=n){\n\t\t\t\tans+=(1ll*phi(i)*pw(n,n\/i-1))%MOD;\n\t\t\t}\n\t\t\tans%=MOD;\n\/\/\t\t\tprintf(\"%d %lld\\n\",i,ans);\n\t\t}\n\t}\n\tprintf(\"%lld\\n\",ans);\n}\nint main(){\n\tint T;\n\tscanf(\"%d\",&T);\n\twhile(T--){\n\t\tinit();\n\t}\n\treturn 0;\n}\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"Polya\u5b9a\u7406\u662f\u4e00\u4e2a\u5173\u4e8e\u7f6e\u6362\u7fa4\u4e2d\u7ec4\u5408\u8ba1\u6570\u7684\u5b9a\u7406\u3002 \u9996\u5148\u6211\u4eec\u6765\u4e86\u89e3Burnside\u5f15\u7406\u3002\u8fd9\u4e2a\u5f15\u7406\u7684\u8bc1\u660e\u8f83\u4e3a\u590d\u6742\uff0c … <\/p>\n