整个欢乐赛#69 就这一题有点难度。
想要证明的话需要一些数论知识。
> 求证：(a mod m+b mod m) mod m=(a+b) mod m(a\bmod m+b\bmod m)\bmod m=(a+b)\bmod m(amodm+bmodm)modm=(a+b)modm（a,b,ma,b,ma,b,m 为整数）。
> 令 a=k1m+a mod m,b=k2m+b mod ma=k_1m+a\bmod m,b=k_2m+b\bmod ma=k1 m+amodm,b=k2 m+bmodm（k1,k2k_1,k_2k1 ,k2 为整数），
> 则 (a+b) mod m=(k1m+a mod m+k2m+b mod m) mod m=(a mod m+b mod m) mod m(a+b)\bmod m=(k_1m+a\bmod m+k_2m+b\bmod m)\bmod m=(a\bmod m+b\bmod m)\bmod m(a+b)modm=(k1 m+amodm+k2 m+bmodm)modm=(amodm+bmodm)modm。
> 注意此处 m∣(k1m,k2m)m\mid(k_1m,k_2m)m∣(k1 m,k2 m)。
> 求证：(a mod m)×(b mod m) mod m=a×b mod m(a\bmod m)\times(b\bmod m)\bmod m=a\times b\bmod m(amodm)×(bmodm)modm=a×bmodm（a,b,ma,b,ma,b,m 为整数）。
> 令 a=k1m+a mod m,b=k2m+b mod ma=k_1m+a\bmod m,b=k_2m+b\bmod ma=k1 m+amodm,b=k2 m+bmodm（k1,k2k_1,k_2k1 ,k2 为整数），
> 则 a×b mod m=(k1m+a mod m)×(k2m+b mod m) mod m=[k1m×k2m+k1m×(b mod m)+(a mod m)×k2m+(a mod m)×(b mod m)] mod m=(a mod m)×(b mod m) mod ma\times b\bmod m=(k_1m+a\bmod m)\times(k_2m+b\bmod m)\bmod m=[k_1m\times k_2m+k_1m\times(b\bmod m)+(a\bmod m)\times k_2m+(a\bmod m)\times(b\bmod m)]\bmod m=(a\bmod
> m)\times(b\bmod m)\bmod ma×bmodm=(k1 m+amodm)×(k2 m+bmodm)modm=[k1 m×k2 m+k1 m×(bmodm)+(amodm)×k2 m+(amodm)×(bmodm)]modm=(amodm)×(bmodm)modm。
> 注意此处 m∣[k1m×k2m,k1m×(b mod m),(a mod m)×k2m]m\mid[k_1m\times k_2m,k_1m\times(b\bmod m),(a\bmod m)\times k_2m]m∣[k1 m×k2 m,k1 m×(bmodm),(amodm)×k2 m]。
根据以上的两个证明，可知边做边取模并不影响计算的结果，所以就有了 40 pts 代码：
注意到上面加粗的文字，这种做法并不会影响到计算的结果，但会影响到你的选择。
> 口胡 hack：
> 上一轮 xxx 变为 109+710^9+7109+7，取模后为 000。
> 此时 yi=1,zi=2y_i=1,z_i=2yi =1,zi =2，你的代码会选择 x+yix+y_ix+yi 操作，使其变为 111。
> 但实际上 x+yix+y_ix+yi 操作会使 xxx 变为 109+810^9+8109+8，而 x×zix\times z_ix×zi 操作会使 xxx 变为 2×109+142\times10^9+142×109+14，应选择后者。
但这并不意味着你不能边做边取模。
注意到 yi,ziy_i,z_iyi ,zi 远小于模数，那么当至少完成一次取模时，若 zi≥2z_i\ge2zi ≥2，那么一定选择 x×zix\times z_ix×zi 操作，否则一定选择 x+yix+y_ix+yi 操作。
好的，100 pts 代码：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
以上全文共 1781 字符，肝了 40+ min，创作不易，点个赞扒。
