\u9898\u76ee\u5927\u610f\uff1a\u6c42\u5f0f\u5b50\uff1a
\n$$\\sum_{i=1}^{n}\\sum_{j=1}^{m}(n\\ mod\\ i)*(m\\ mod\\ j) (i \\ne j)$$
\n\u7684\u503c\u3002<\/p>\n
\u90a3\u4e48\u5bb9\u65a5\u4ee5\u540e\u7b49\u4ef7\u4e8e\u6c42\uff1a
\n$$\\sum_{i=1}^{n}\\sum_{j=1}^{m}(n\\ mod\\ i)*(m\\ mod\\ j)-\\sum_{i=1}^{min(n,m)}(n\\ mod\\ i)*(m\\ mod\\ i)$$<\/p>\n
\u9996\u5148\u6c42\uff1a
\n$$\\sum_{i=1}^{n}\\sum_{j=1}^{m}(n\\ mod\\ i)*(m\\ mod\\ j)$$<\/p>\n
\u9996\u5148\uff0c\u6211\u4eec\u6709\u5b9a\u7406\uff1a
\n$$ n\\ mod\\ p=n-p*\\lfloor \\frac{n}{p} \\rfloor$$
\n\u7136\u540e\u914d\u5408\u4e0a\\(\\Sigma\\)\u7684\u8fd0\u7b97\u6cd5\u5219\uff0c\u6211\u4eec\u53ef\u4ee5\u628a\u539f\u5f0f\u8f6c\u5316\u4e3a\uff1a
\n$$n^{2}*m^{2}-m^{2}\\sum_{i=1}^{n}i\\lfloor \\frac{n}{i} \\rfloor-n^{2}\\sum_{j=1}^{m}j\\lfloor \\frac{m}{j} \\rfloor-\\sum_{i=1}^{n}i\\lfloor \\frac{n}{i} \\rfloor \\sum_{j=1}^{m}j\\lfloor \\frac{m}{j} \\rfloor$$
\n\u6211\u4eec\u8bbe\uff1a
\n$$ P=\\sum_{i=1}^{n}i\\lfloor \\frac{n}{i} \\rfloor,Q=\\sum_{j=1}^{m}j\\lfloor \\frac{m}{j} \\rfloor$$
\n\u6240\u4ee5\u6211\u4eec\u53ef\u4ee5\u7528\u6570\u8bba\u5206\u5757\u6765\u5206\u522b\u8ba1\u7b97\\(P,Q\\)\u7684\u503c\u3002<\/p>\n
\u800c\uff0c\u5bf9\u4e8e\u7b2c\u4e8c\u90e8\u5206\uff1a
\n$$R=\\sum_{i=1}^{min(n,m)}(n\\ mod\\ i)*(m\\ mod\\ i)$$
\n\u6211\u4eec\u4e0d\u59a8\u4ee4\\(n<m\\)
\n\u90a3\u4e48\u5c06\u539f\u5f0f\u5c55\u5f00\uff0c\u53ef\u5f97\uff1a
\n$$R=\\sum_{i=1}^{n}n*m-n*i\\lfloor \\frac{m}{i} \\rfloor-m*i\\lfloor \\frac{n}{i} \\rfloor+i^{2}\\lfloor \\frac{n}{i} \\rfloor \\lfloor \\frac{m}{i} \\rfloor$$
\n\u8fd9\u4e2a\u5f0f\u5b50\u663e\u7136\u4e5f\u662f\u53ef\u4ee5\u6570\u8bba\u5206\u5757\u7684\u3002\u4f46\u662f\u6211\u4eec\u9700\u8981\u8ba1\u7b97\\(i^{2}\\)\u5bf9\u4e8e\u5f0f\u5b50\u7684\u8d21\u732e\u3002
\n\u7528\u4e00\u4e9b\u7b80\u5355\u7684\u8bc1\u660e\u65b9\u6cd5\u53ef\u4ee5\u5f97\u5230\uff1a
\n$$\\sum_{i=1}^{n}i^{2}=\\frac{n(2n+1)(n+1)}{6}$$
\n\u90a3\u4e48\u5b83\u7684\u533a\u95f4\u548c\u5373\u662f\uff1a
\n$$\\sum_{i=1}^{r}i^{2}-\\sum_{i=1}^{l-1}i^{2}=\\frac{(2r^2+2rl+2l^2-r-3l+2)(r-l+1)}{6}$$
\n\u4e8e\u662f\u6211\u4eec\u5c31\u53ef\u4ee5\u7edf\u8ba1\u6574\u4e2a\u7ed3\u679c\u4e86\u3002<\/p>\n
\u73b0\u5728\u6211\u4eec\u6765\u8003\u8651\u6570\u8bba\u5206\u5757\u3002<\/p>\n
\u6570\u8bba\u5206\u5757\u662f\u4e00\u79cd\u5904\u7406\u5f62\u5982
\n$$ \\sum_{i=1}^{n}\\lfloor \\frac{n}{i} \\rfloor$$
\n\u7684\u516c\u5f0f\u7684\u6c42\u503c\u7684\u65b9\u6cd5\u3002<\/p>\n
\u800c\u5bf9\u4e8e\u51fd\u6570\uff1a<\/p>\n
$$f(x)=\\lfloor \\frac{a}{x} \\rfloor$$<\/p>\n
\u53ef\u4ee5\u53d1\u73b0\uff0c\u5bf9\u4e8e\u8fde\u7eed\u7684\u4e00\u6bb5\\(x\\)\u7684\u533a\u95f4\uff0c\u5b83\u7684\u503c\u662f\u76f8\u540c\u7684\u3002
\n\u5177\u4f53\u6765\u8bf4\u662f\uff0c\u4ee4\u503c\u4e3a\\(k\\)\u5219\uff0c\u4ee4\u533a\u95f4\u7684\u5de6\u7aef\u70b9\u4e3a\\(l\\)\uff0c\u5219\u6574\u4e2a\u533a\u95f4\u7684\u503c\u4e3a\uff1a
\n$$k=\\lfloor \\frac{n}{l} \\rfloor$$
\n\u90a3\u4e48\u53f3\u7aef\u70b9\\(r\\)\u5f88\u663e\u7136\u662f\u6ee1\u8db3\u65b9\u7a0b\uff1a
\n$$\\lfloor \\frac{n}{x} \\rfloor=k$$
\n\u7684\u6700\u5927\u503c\u3002
\n\u4f9d\u636e\u6574\u9664\u7684\u6027\u8d28\u5f97\u5230\u7684\u5f15\u7406\u4e00\uff0c\u6211\u4eec\u53d1\u73b0\uff1a
\n$$r=\\lfloor \\frac{n}{k} \\rfloor$$
\n\u4ece\u800c\uff0c\u533a\u95f4\u4e3a\uff1a
\n$$[l,\\lfloor \\frac{n}{\\lfloor \\frac{n}{l} \\rfloor} \\rfloor$$<\/p>\n
\u9644\uff1a\u5bf9\u4e8e\u5f15\u7406\u4e00\u7684\u8bc1\u660e\uff1a<\/p>\n
\u5f15\u7406\u4e00\uff1a\u6c42\u8bc1\u65b9\u7a0b\uff1a
\n$$\\lfloor \\frac{n}{x} \\rfloor=k$$
\n\u7684\u89e3\u7684\u6700\u5927\u503c\\(t\\)\u4e3a
\n$$t=\\lfloor \\frac{n}{k} \\rfloor$$
\n\u6211\u4eec\u4ee4\u65b9\u7a0b\u7684\u4e00\u4e2a\u5408\u6cd5\u89e3\\(x\\)\u6ee1\u8db3\uff1a
\n$$x*k+r=n\\ (0\\le r < x)\\ (1)$$
\n\u5e76\u4ee4\uff1a
\n$$t=x+d$$
\n\u90a3\u4e48\uff0c\u6709\uff1a
\n$$\\lfloor \\frac{n}{x+d} \\rfloor=k$$
\n\u5219\uff1a
\n$$(x+d)*k+r’=n\\ (0\\le r < x+d)\\ (2)$$
\n\u8054\u7acb\u65b9\u7a0b\\((1),(2)\\)\u53ef\u5f97\uff1a
\n$$d*k+r’=r$$
\n\u7531\u6574\u9664\u7684\u5b9a\u4e49\u53ef\u5f97\uff1a
\n$$d=\\lfloor \\frac{r}{k} \\rfloor$$
\n\u5f88\u663e\u7136\uff0c\u5f53
\n$$x=\\lfloor \\frac{n}{k} \\rfloor$$
\n\u65f6\uff0c
\n$$r=n\\ mod\\ k,r<k,\\lfloor \\frac{r}{k} \\rfloor=0$$
\n\u6b64\u65f6\\(x\\)\u53d6\u5230\u6700\u5927\u503c\u3002
\n\u8bc1\u6bd5\u3002<\/p>\n
\u53e6\uff1a\u5c3d\u91cf\u7528\u6a21\u5757\u5316\u7f16\u7a0b\uff0c\u800c\u4e0d\u662f\u53bb\u5316\u7b80\u5f0f\u5b50\u3002\u8fd9\u6837\u53ef\u4ee5\u7528\u590d\u6742\u5ea6\u6362\u53d6\u6b63\u786e\u7387\u3002<\/p>\n
#include<iostream>\r\n#include<cstdio>\r\nconst long long MOD = 19940417;\r\nconst long long inv2 = 9970209;\r\nconst long long inv6 = 3323403;\r\nlong long n,m;\r\ninline long long sm1(long long A){\r\n return (A*(A+1)%MOD)*inv2%MOD;\r\n}\r\ninline long long sm2(long long A){\r\n return ((A*(A+1)%MOD)*(2*A+1)%MOD)*inv6%MOD;\r\n}\r\nvoid init(){\r\n scanf(\"%lld%lld\",&n,&m);\r\n n>m?n^=m^=n^=m:0; \r\n long long P,Q,R;\r\n int l,r;\r\n r=0,P=0;\r\n while(r<n){\r\n l=r+1;\r\n r=(n\/l)?(n\/(n\/l)):n;\r\n P+=(((r-l+1)*(n\/l)%MOD)*(l+r)%MOD*inv2)%MOD;\r\n P%=MOD;\r\n\/\/ printf(\"P:%lld\\n\",P);\r\n }\r\n P%=MOD;\r\n r=0,Q=0;\r\n while(r<m){\r\n l=r+1;\r\n r=(m\/l)?(m\/(m\/l)):m;\r\n Q+=(((r-l+1)*(m\/l)%MOD)*(l+r)%MOD*inv2)%MOD;\r\n Q%=MOD;\r\n\/\/ printf(\"Q:%lld\\n\",Q);\r\n }\r\n\/\/ printf(\"%lld %lld\\n\",P,Q);\r\n Q%=MOD;\r\n R=(n*m%MOD)*n%MOD;\r\n long long ans=(n*m%MOD)*(n*m%MOD)%MOD-(n*n%MOD)*Q%MOD-(m*m%MOD)*P%MOD+P*Q%MOD;\r\n ans%=MOD;\r\n ans+=MOD;\r\n ans%=MOD;\r\n r=0;\r\n while(r<n){\r\n l=r+1;\r\n r=std::min((n\/l)?(n\/(n\/l)):n,(m\/l)?(m\/(m\/l)):m);\r\n CNT1=m\/l;\r\n CNT2=n\/l;\r\n R-=((((sm1(r)-sm1(l-1))%MOD)*(m\/l)%MOD)*n%MOD+(((sm1(r)-sm1(l-1))%MOD)*(n\/l)%MOD)*m%MOD);\r\n R+=(((sm2(r)-sm2(l-1))%MOD)*((m\/l)*(n\/l)%MOD))%MOD;\r\n R%=MOD;\r\n }\r\n ans-=R;\r\n ans%=MOD;\r\n ans+=MOD;\r\n ans%=MOD;\r\n printf(\"%lld\",ans);\r\n \r\n}\r\nint main(){\r\n init();\r\n return 0;\r\n}<\/code><\/pre>\n <\/p>\n","protected":false},"excerpt":{"rendered":"
\u9898\u76ee\u5927\u610f\uff1a\u6c42\u5f0f\u5b50\uff1a $$\\sum_{i=1}^{n}\\sum_{j=1}^{m}(n\\ mod\\ i)*(m\\ … <\/p>\n