首先，第一步列出方程式，公母小分别为 a,b,ca,b,ca,b,c 。可得以下式子。
{a+b+c=n5a+3b+c3=n\begin{cases}a+b+c=n\\ 5a+3b+\frac{c}{3}=n\end{cases}{a+b+c=n5a+3b+3c =n
由第一条式子，可以得出 c=n−a−bc=n-a-bc=n−a−b
代入第二条式子，得到
5a+3b+n−a−b3=n15a+9b+(n−a−b)=3n14a+8b=2n7a+4b=n5a+3b+\frac{n-a-b}{3}=n\\ 15a+9b+(n-a-b)=3n\\ 14a+8b=2n\\ 7a+4b=n5a+3b+3n−a−b =n15a+9b+(n−a−b)=3n14a+8b=2n7a+4b=n
然后，由上式得出， b=n−7a4b=\frac{n-7a}{4}b=4n−7a ，由于 bbb 是整数，所以得出 n−7a≡0(mod4)n-7a \equiv 0 \pmod{4}n−7a≡0(mod4)
这等价于 7a≡n(mod4)7a \equiv n \pmod{4}7a≡n(mod4)
接着， 7≡3(mod4)7 \equiv 3 \pmod{4}7≡3(mod4) ，因此上式等同于 3a≡n(mod4)3a \equiv n \pmod{4}3a≡n(mod4)
小知识： 对于非零整数 a,ma,ma,m ，如果存在 bbb 使得 ab≡1(modm)ab\equiv 1\pmod mab≡1(modm)，就称 bbb 是 aaa 在模 mmm 意义下的逆元。摘自Oiwiki中模逆元一章
不难发现，333 在 mod 4\mod 4mod4 下的逆元是 333 (3×3=9,9≡1(mod4)3\times 3 = 9 , 9 \equiv 1 \pmod{4}3×3=9,9≡1(mod4))
故 a≡3n(mod4)a \equiv 3n \pmod{4}a≡3n(mod4)
这就是优化核心！aaa 对 444 取模的值是固定的！
最后，设 a0=3nmod 4a_0 = 3n \mod 4a0 =3nmod4 ，那么所有满足条件的 aaa 可以表示为 ak=a0+4ka_k = a_0 + 4kak =a0 +4k ，其中 k∈Rk \in \mathbf{R}k∈R
不难看出这是个等差数列，答案即为这个等差数列的项数，这个数列的项数是 ⌊n7−a04⌋+1\left\lfloor\dfrac{\frac{n}{7}-a_0}{4}\right\rfloor +1⌊47n −a0 ⌋+1
附上代码：
