\u8fd9\u662f\u4e00\u9053\u4e2d\u56fd\u5269\u4f59\u5b9a\u7406\uff08\u53c8\u540d\u5b59\u5b50\u5b9a\u7406\u3001CRT\uff09\u7684\u6a21\u677f\u9898\u3002
\n\u5b83\u6700\u65e9\u6765\u81ea\u4e8e\u300c\u5b59\u5b50\u7b97\u7ecf\u300d\uff0c\u5f62\u5f0f\u5316\u7684\u8bf4\uff0c\u5b83\u662f\u4e00\u79cd\u7528\u4e8e\u6c42\u89e3\u5982\u4e0b\u7684\u7ebf\u6027\u540c\u4f59\u65b9\u7a0b\u7ec4\u7684\u89e3\u7684\u7b97\u6cd5\u3002
\n$$ \\left\\{ \\begin{matrix}x\\equiv a_{1} \\pmod{p_1} \\\\x\\equiv a_{2}\\pmod{p_2}\\\\\\cdots\\\\x\\equiv a_{n}\\pmod{p_i}\\end{matrix} \\right.$$
\n\u6211\u4eec\u4ee4\uff1a
\n$$\\begin{equation}\\begin{split}P&=&\\prod_{i=1}^{n}p_{i}\\\\t_{i},st: \\frac{P}{p_{i}}t_{i}&\\equiv &1\\pmod{p_i}\\\\\\exists x,st: x&\\equiv &\\sum_{i=1}^n \\frac{P}{p_{i}}a_{i}t_{i}\\\\x&\\in&\\{x_0+kP,k\\in Z\\pmod{P}\\}\\end{split}\\end{equation}$$
\n\u7136\u800c\u8fd9\u662f\u600e\u4e48\u8bc1\u660e\u7684\u5462\uff1f\u6211\u4eec\u6709\u5982\u4e0b\u63a8\u5bfc\uff1a
\n$$\\begin{equation}\\begin{split}\\forall i,\\forall j,st:i\\neq j, a_{i}t_{i}\\frac{P}{p_{i}}&\\equiv&0&\\pmod{p_i}\\\\a_{i}t_{i}\\frac{P}{p_i}&\\equiv&a_{i} &\\pmod{p_i}\\\\\\forall j,\\sum_{i=1}^{n}a_{i}t_{i}\\frac{P}{p_{i}}&\\equiv&a_{j}t_{j}\\frac{P}{p_{j}} \\equiv a_{j}&\\pmod{p_{j}}\\\\\\exists x_0&\\equiv& \\sum_{i=1}^{n}a_{i}t_{i}\\frac{P}{p_{i}}&\\pmod{p_{j}}\\\\\\end{split}\\end{equation}$$
\n\u6545\u800c\u6211\u4eec\u5c31\u53ef\u4ee5\u6c42\u5f97\u4e0a\u8ff0\u65b9\u7a0b\u7684\u6700\u5c0f\u6b63\u6574\u6570\u89e3\u3002
\n\u53e6\u5916\uff0c\u770b\u5230\u8fd9\u9898\u7684\u6570\u636e\u8303\u56f4\u5c31\u53ef\u4ee5\u731c\u5230\u53c8\u662f\u9f9f\u901f\u4e58\u767b\u573a\u7684\u65f6\u523b\u4e86\u3002
\n\u8fd9\u4e00\u9898\u8fd8\u6709\u4e2a\u5751\u70b9\u5c31\u662f\u8bfb\u5165\u7684\u6570\u53ef\u80fd\u662f\u8d1f\u6570\u2026 <\/p>\n\n\n\n
#include<iostream>\n#include<cstdio>\n\nlong long MOD=1;\n\n\ninline long long mlt(long long A,long long X){\n\tlong long BS=A,RT=0;\n\twhile(X){\n\t\tif(X&1){\n\t\t\tRT+=BS;\n\t\t\tRT%=MOD;\n\t\t}\n\t\tBS+=BS;\n\t\tBS%=MOD;\n\t\tX>>=1;\n\t}\n\treturn RT;\n}\ninline long long exgcd(long long A,long long B,long long &X,long long &Y,long long D=0){\n\treturn B?(D=exgcd(B,A%B,Y,X),Y-=A\/B*X,D):(X=1,Y=0,A);\n}\ninline long long pw(long long A,long long X){\n\tlong long BS=A,RT=1;\n\twhile(X){\n\t\tif(X&1){\n\t\t\tRT=mlt(RT,BS)%MOD;\n\t\t}\n\t\tBS=mlt(BS,BS)%MOD;\n\t\tX>>=1;\n\t}\n\treturn RT;\n}\nlong long n,a[100005],b[100005];\nvoid init(){\n\tscanf(\"%lld\",&n);\n\tfor(int i=1;i<=n;++i){\n\t\tscanf(\"%lld\",&a[i]);\n\t}\n\tfor(int i=1;i<=n;++i){\n\t\tscanf(\"%lld\",&b[i]);\n\t\ta[i]=(a[i]%b[i]+b[i])%b[i];\/\/\u6ce8\u610f\u8d1f\u6570\uff01\uff01 \n\t\tMOD*=b[i];\n\t}\n\tlong long X,Y,T,ans=0;\n\tfor(int i=1;i<=n;++i){\n\t\tT=MOD\/b[i];\n exgcd(T,b[i],X,Y);\n X=(X%b[i]+b[i])%b[i];;\n ans=(ans+mlt(mlt(T,X),a[i]))%MOD;\n\t}\n\tprintf(\"%lld\\n\",(ans+MOD)%MOD);\n}\n\nint main(){\n\tinit();\n\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u8fd9\u662f\u4e00\u9053\u4e2d\u56fd\u5269\u4f59\u5b9a\u7406\uff08\u53c8\u540d\u5b59\u5b50\u5b9a\u7406\u3001CRT\uff09\u7684\u6a21\u677f\u9898\u3002 \u5b83\u6700\u65e9\u6765\u81ea\u4e8e\u300c\u5b59\u5b50\u7b97\u7ecf\u300d\uff0c\u5f62\u5f0f\u5316\u7684\u8bf4\uff0c\u5b83\u662f\u4e00\u79cd\u7528\u4e8e\u6c42\u89e3 … <\/p>\n