\u66fe\u7ecf\u6709\u4e00\u9053\u9898\uff0c\u53eb\u505aYY\u7684GCD\uff0c\u5b83\u6c42\u7684\u662f\u8fd9\u6837\u4e00\u4e2a\u503c\uff1a
$$\\begin{equation}\\begin{split}\\sum_{x=1}^{n}\\sum_{y=1}^{m}\\sum_{p\\in P}[gcd(x,y)==p] \\end{split}\\end{equation}$$
\u7136\u540e\u89c2\u5bdf\u8fd9\u9053\u9898\u7684\u6c42\u548c\u5f0f\uff1a
$$\\begin{equation}\\begin{split}\\sum_{x=1}^{n}\\sum_{y=1}^{m}[gcd(x,y)==d] \\end{split}\\end{equation}$$
\u957f\u5f97\u5f88\u50cf\u5bf9\u4e0d\u5bf9\uff1f
\u4e8b\u5b9e\u4e0a\u5c31\u662f\u524d\u8005\u7684\u7b80\u5316\u7248\u3002
\u5269\u4e0b\u7684\u64cd\u4f5c\u5c31\u5f88\u5957\u8def\u4e86\u3002
$$\\begin{equation}\\begin{split}&\\sum_{x=1}^{\\lfloor\\frac{n}{d}\\rfloor}\\sum_{y=1}^{\\lfloor\\frac{m}{d}\\rfloor}[gcd(x,y)==1]\\\\=&\\sum_{x=1}^{\\lfloor\\frac{n}{d}\\rfloor}\\sum_{y=1}^{\\lfloor\\frac{m}{d}\\rfloor}\\sum_{k|gcd(x,y)}\\mu(k)\\\\=&\\sum_{x=1}^{\\lfloor\\frac{n}{dk}\\rfloor}\\sum_{y=1}^{\\lfloor\\frac{m}{dk}\\rfloor}\\mu(k)\\\\=&\\sum_{k=1}^{min(n,m)}\\mu(k)\\lfloor\\frac{n}{dk}\\rfloor\\lfloor\\frac{m}{dk}\\rfloor \\end{split}\\end{equation}$$
\u7136\u540e\u9884\u5904\u7406\u51fa\u83ab\u6bd4\u4e4c\u65af\u51fd\u6570\u8dd1\u6570\u8bba\u5206\u5757\u5373\u53ef\u3002<\/p>\n\n\n\n
#include<iostream>\n#include<cstdio>\n\nconst int N = 100000+5;\n\nint p[N\/10],mu[N],n,m,d;\nbool ip[N];\nvoid prpr(){\n\tp[0]=0;mu[1]=1;ip[1]=1;\n\tfor(int i=2;i<=100000;++i){\n\t\tif(!ip[i]){\n\t\t\tp[++p[0]]=i;\n\t\t\tmu[i]=-1;\n\t\t}\n\t\tfor(int j=1;j<=p[0]&&p[j]*i<=100000;++j){\n\t\t\tip[i*p[j]]=1;\n\t\t\tif(!(i%p[j])){\n\t\t\t\tmu[i*p[j]]=0;\n\t\t\t\tbreak;\n\t\t\t}else{\n\t\t\t\tmu[i*p[j]]=-mu[i];\n\t\t\t}\n\t\t}\n\t}\n\tfor(int i=2;i<=100000;++i){\n\t\tmu[i]+=mu[i-1]; \n\t}\n}\nlong long ans;\nvoid init(){\n\tscanf(\"%d%d%d\",&n,&m,&d);\n\tn>m?n^=m^=n^=m:0;\n\tans=0;\n\tint k=0;\n\tfor(int i=1;i<=n;i=k+1){\n\t\tk=std::min(n\/(n\/i),m\/(m\/i));\n\t\tans+=1ll*(n\/(i*d))*(m\/(i*d))*(mu[k]-mu[i-1]);\n\t}\n\tprintf(\"%lld\\n\",ans);\n}\n\nint main(){\n\tprpr();\n\tint T;\n\tscanf(\"%d\",&T);\n\twhile(T--){\n\t\tinit();\n\t}\n\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u66fe\u7ecf\u6709\u4e00\u9053\u9898\uff0c\u53eb\u505aYY\u7684GCD\uff0c\u5b83\u6c42\u7684\u662f\u8fd9\u6837\u4e00\u4e2a\u503c\uff1a $$\\begin{equation}\\begin{spl … <\/p>\n