对每个正整数 $n$，记 $g(n)$ 为 $n$ 与2015的最大公约数，求满足下列条件的有序三元数组 $(a,b,c)$ 的个数：
1）$a,b,c\in \{1,2,\cdots ,2015\}$；
2）$g(a),g(b),g(c),g(a+b),g(b+c),g(c+a),g(a+b+c)$ 这七个数两两不同．
1）$a,b,c\in \{1,2,\cdots ,2015\}$；
2）$g(a),g(b),g(c),g(a+b),g(b+c),g(c+a),g(a+b+c)$ 这七个数两两不同．
【难度】
【出处】
2015第14届CGMO试题
【标注】
【答案】
$138240$
【解析】
分解质因数 $2015=5\times13\times 31={{p}_{1}}\times {{p}_{2}}\times {{p}_{3}}$．$g(n)$ 是2015的约数，只有8种情况．我们把满足 $g(n)=1$ 的 $n$ 叫做零型数，把满足 $g(n)$ 取 ${{p}_{1}}$ 或 ${{p}_{2}}$ 或 ${{p}_{3}}$ 的 $n$ 叫做一型数，把满足 $g(n)$ 取 ${{p}_{1}}{{p}_{2}}$ 或 ${{p}_{1}}{{p}_{3}}$ 或 ${{p}_{2}}{{p}_{3}}$ 的 $n$ 叫做二型数．
我们使用下面两个简单的事实：
对任意整数 $x$，$g(x)=g(-x)=g(2015+x)=g(2015-x)$，因此本题可以看做在模2015意义下讨论，即模2015同余的两个数看成相同．
对素数 $p$，若 $p|x$，$p|y$ 两者都成立则 $p|x\pm y$，若恰有一个成立则 $p\not{|}x\pm y$．
把满足条件三元组 $(a,b,c)$ 对应为七元组 $A=(a,b,c,a+b,a+c,b+c,a+b+c)$，我们考虑A的七个位置上的数的 $g$ 值的分布．首先这七个 $g$ 值不能有2015，否则，若某个位置上的数 $x$ 是2015的倍数，则A中存在另外两个位置上的数 $y,z$ 满足 $x=y+z$ 或 $x=y-z$，这样就有 $g(y)=g(z)$，矛盾．所以七个 $g$ 值必须是1，${{p}_{1}}$，${{p}_{2}}$，${{p}_{3}}$，${{p}_{1}}{{p}_{2}}$，${{p}_{1}}{{p}_{3}}$，${{p}_{2}}{{p}_{3}}$ 各一个．这样A的七个位置必须是3个二型数、3个一型数、一个零型数．我们关心三个二型数在哪三个位置上．
设 ${{p}_{1}},{{p}_{2}},{{p}_{3}}$ 是5，13，31的任意排列，若 $x,y,z$ 满足 $g(x)={{p}_{1}}{{p}_{2}}$，$g(y)={{p}_{1}}{{p}_{3}}$，$g(z)={{p}_{2}}{{p}_{3}}$，则有 ${{p}_{1}}|x,{{p}_{1}}|y\Rightarrow{{p}_{1}}|\pm x\pm y$，${{p}_{2}}|x,{{p}_{2}}\not{|}y\Rightarrow{{p}_{2}}\not{|}\pm x\pm y$，${{p}_{3}}\not{|}x,{{p}_{3}}|y\Rightarrow{{p}_{3}}\not{|}\pm x\pm y$，可得 $g(\pm x\pm y)={{p}_{1}}$，同理有 $g(\pm x\pm z)={{p}_{2}}$，$g(\pm y\pm z)={{p}_{3}}$，$g(\pm x\pm y\pm z)=1$．因此当确定A中的三个二型数 $x,y,z$ 的位置后，如果其它四个位置可以分别表示为 $x,y,z$ 的3个两两线性组合与 $x,y,z$ 三个数的线性组合（要求线性组合系数是 $\pm 1$），我们就可断定A中的七个位置的 $g$ 值互不相同，我们把这种可以线性组合成功表示的三个二型数的一组位置叫做合理位置．在一组合理位置上，当我们确定 $x,y,z$ 的取值（模2015意义下）后，七元组A也被唯一决定了．在模2015意义下，满足 $g(n)={{p}_{1}}{{p}_{2}}$ 的 $n$ 恰好有 ${{p}_{3}}-1$ 个，满足 $g(n)={{p}_{1}}{{p}_{3}}$ 的 $n$ 恰好有 ${{p}_{2}}-1$ 个，满足 $g(n)={{p}_{2}}{{p}_{3}}$ 的 $n$ 恰好有 ${{p}_{1}}-1$ 个，此外 $x,y,z$ 的顺序或者说 ${{p}_{1}},{{p}_{2}},{{p}_{3}}$ 的顺序可以调换，因此每组合理位置下，$x,y,z$ 的取值有 $3!\times({{p}_{3}}-1)({{p}_{2}}-1)({{p}_{1}}-1)=6\times 1440=8640$ 种可能，也就恰好对应8640个满足条件的三元组．
我们关心哪组位置可能是合理的．对素数 $p=5,13,31$，七元组A中恰好有3个位置是 $p$ 的倍数，若 $a+b,a+c,b+c$ 这三个位置至少有两个 $p$ 的倍数，不妨设 $p|a+b,p|a+c$，则在此前提下 $p|a\Leftrightarrow p|b\Leftrightarrow p|c\Leftrightarrow p|a+b+c$ 并且 $p|b+c\Rightarrow p|(a+b)+(a+c)-(b+c)\Rightarrow p|2a\Rightarrow p|a$，这时A中不能恰有3个位置是 $p$ 的倍数．所以 $g(a+b)$，$g(a+c)$，$g(b+c)$ 的素因子个数总共不超过3，$a+b,a+c,b+c$ 这三个位置上至多有一个二型数，也就是 $a,b,c,a+b+c$ 这四个位置上有2或3个二型数．
若 $a,b,c,a+b+c$ 中有三个二型数，二型数的位置有4种可能情况：
若 $x=a,y=b,z=c$ 是三个二型数，则 $a+b=x+y$，$a+c=x+z$，$b+c=y+z$ 是三个一型数，$a+b+c=x+y+z$ 是零型数，位置合理．
若 $x=a,y=b,z=a+b+c$ 是二型数，则 $a+b=x+y,b+c=z-x,a+c=z-y$，$c=-x-y+z$，位置合理．同理其他两种位置也是合理的．
若 $a,b,c,a+b+c$ 中恰有两个二型数，我们分两类考虑：
第一类考虑两个二型数都在 $a,b,c$ 中，不妨设 $a$ 和 $b$ 是二型数，则 $a+b$ 不可能是二型数，$a+c$，$b+c$ 之一是二型数，不妨设 $a+c$ 是二型数．这时 $x=a,y=b,z=a+c$ 是三个二型数，$a+b=x+y,c=-x+z,a+b+c=y+z$，$b+c=-x+y+z$，位置合理．这一类由对称性共有6种情况是合理位置．
第二类考虑 $a+b+c$ 是二型数且 $a,b,c$ 之一是二型数，不妨设 $a$ 和 $a+b+c$ 是二型数，则 $b+c$ 不可能是二型数，$a+b$，$a+c$ 之一是二型数，不妨设 $a+b$ 是二型数．这时 $x=a,y=a+b+c,z=a+b$ 是二型数，则 $b+c=-x+y,b=-x+z,c=y-z$，$a+c=x+y-z$，位置合理．这一类由对称性共有6种情况是合理位置．
综上，三个二型数的合理位置共有16种，（其他不合理位置都不可能使三元组满足条件）．所以满足条件的三元组共有 $16\times 8640=138240$．
我们使用下面两个简单的事实：
对任意整数 $x$，$g(x)=g(-x)=g(2015+x)=g(2015-x)$，因此本题可以看做在模2015意义下讨论，即模2015同余的两个数看成相同．
对素数 $p$，若 $p|x$，$p|y$ 两者都成立则 $p|x\pm y$，若恰有一个成立则 $p\not{|}x\pm y$．
把满足条件三元组 $(a,b,c)$ 对应为七元组 $A=(a,b,c,a+b,a+c,b+c,a+b+c)$，我们考虑A的七个位置上的数的 $g$ 值的分布．首先这七个 $g$ 值不能有2015，否则，若某个位置上的数 $x$ 是2015的倍数，则A中存在另外两个位置上的数 $y,z$ 满足 $x=y+z$ 或 $x=y-z$，这样就有 $g(y)=g(z)$，矛盾．所以七个 $g$ 值必须是1，${{p}_{1}}$，${{p}_{2}}$，${{p}_{3}}$，${{p}_{1}}{{p}_{2}}$，${{p}_{1}}{{p}_{3}}$，${{p}_{2}}{{p}_{3}}$ 各一个．这样A的七个位置必须是3个二型数、3个一型数、一个零型数．我们关心三个二型数在哪三个位置上．
设 ${{p}_{1}},{{p}_{2}},{{p}_{3}}$ 是5，13，31的任意排列，若 $x,y,z$ 满足 $g(x)={{p}_{1}}{{p}_{2}}$，$g(y)={{p}_{1}}{{p}_{3}}$，$g(z)={{p}_{2}}{{p}_{3}}$，则有 ${{p}_{1}}|x,{{p}_{1}}|y\Rightarrow{{p}_{1}}|\pm x\pm y$，${{p}_{2}}|x,{{p}_{2}}\not{|}y\Rightarrow{{p}_{2}}\not{|}\pm x\pm y$，${{p}_{3}}\not{|}x,{{p}_{3}}|y\Rightarrow{{p}_{3}}\not{|}\pm x\pm y$，可得 $g(\pm x\pm y)={{p}_{1}}$，同理有 $g(\pm x\pm z)={{p}_{2}}$，$g(\pm y\pm z)={{p}_{3}}$，$g(\pm x\pm y\pm z)=1$．因此当确定A中的三个二型数 $x,y,z$ 的位置后，如果其它四个位置可以分别表示为 $x,y,z$ 的3个两两线性组合与 $x,y,z$ 三个数的线性组合（要求线性组合系数是 $\pm 1$），我们就可断定A中的七个位置的 $g$ 值互不相同，我们把这种可以线性组合成功表示的三个二型数的一组位置叫做合理位置．在一组合理位置上，当我们确定 $x,y,z$ 的取值（模2015意义下）后，七元组A也被唯一决定了．在模2015意义下，满足 $g(n)={{p}_{1}}{{p}_{2}}$ 的 $n$ 恰好有 ${{p}_{3}}-1$ 个，满足 $g(n)={{p}_{1}}{{p}_{3}}$ 的 $n$ 恰好有 ${{p}_{2}}-1$ 个，满足 $g(n)={{p}_{2}}{{p}_{3}}$ 的 $n$ 恰好有 ${{p}_{1}}-1$ 个，此外 $x,y,z$ 的顺序或者说 ${{p}_{1}},{{p}_{2}},{{p}_{3}}$ 的顺序可以调换，因此每组合理位置下，$x,y,z$ 的取值有 $3!\times({{p}_{3}}-1)({{p}_{2}}-1)({{p}_{1}}-1)=6\times 1440=8640$ 种可能，也就恰好对应8640个满足条件的三元组．
我们关心哪组位置可能是合理的．对素数 $p=5,13,31$，七元组A中恰好有3个位置是 $p$ 的倍数，若 $a+b,a+c,b+c$ 这三个位置至少有两个 $p$ 的倍数，不妨设 $p|a+b,p|a+c$，则在此前提下 $p|a\Leftrightarrow p|b\Leftrightarrow p|c\Leftrightarrow p|a+b+c$ 并且 $p|b+c\Rightarrow p|(a+b)+(a+c)-(b+c)\Rightarrow p|2a\Rightarrow p|a$，这时A中不能恰有3个位置是 $p$ 的倍数．所以 $g(a+b)$，$g(a+c)$，$g(b+c)$ 的素因子个数总共不超过3，$a+b,a+c,b+c$ 这三个位置上至多有一个二型数，也就是 $a,b,c,a+b+c$ 这四个位置上有2或3个二型数．
若 $a,b,c,a+b+c$ 中有三个二型数，二型数的位置有4种可能情况：
若 $x=a,y=b,z=c$ 是三个二型数，则 $a+b=x+y$，$a+c=x+z$，$b+c=y+z$ 是三个一型数，$a+b+c=x+y+z$ 是零型数，位置合理．
若 $x=a,y=b,z=a+b+c$ 是二型数，则 $a+b=x+y,b+c=z-x,a+c=z-y$，$c=-x-y+z$，位置合理．同理其他两种位置也是合理的．
若 $a,b,c,a+b+c$ 中恰有两个二型数，我们分两类考虑：
第一类考虑两个二型数都在 $a,b,c$ 中，不妨设 $a$ 和 $b$ 是二型数，则 $a+b$ 不可能是二型数，$a+c$，$b+c$ 之一是二型数，不妨设 $a+c$ 是二型数．这时 $x=a,y=b,z=a+c$ 是三个二型数，$a+b=x+y,c=-x+z,a+b+c=y+z$，$b+c=-x+y+z$，位置合理．这一类由对称性共有6种情况是合理位置．
第二类考虑 $a+b+c$ 是二型数且 $a,b,c$ 之一是二型数，不妨设 $a$ 和 $a+b+c$ 是二型数，则 $b+c$ 不可能是二型数，$a+b$，$a+c$ 之一是二型数，不妨设 $a+b$ 是二型数．这时 $x=a,y=a+b+c,z=a+b$ 是二型数，则 $b+c=-x+y,b=-x+z,c=y-z$，$a+c=x+y-z$，位置合理．这一类由对称性共有6种情况是合理位置．
综上，三个二型数的合理位置共有16种，（其他不合理位置都不可能使三元组满足条件）．所以满足条件的三元组共有 $16\times 8640=138240$．
答案
解析
备注
