题意
(S(n,m)={k|n\%k+m\%kge k,kin Z})，给定(n,m)，求(varphi(n)*varphi(m)*sumlimits_{kin S(n,m)}varphi(k))（(n,mle 10^{15})）
做法
结论：(sumlimits_{kin S(n,m)}varphi(k)=n*m)
证明：
对于(kin Z)
(n=q_1k+r_1,m=q_2k+r_2)
若(r1+r2ge k)，(leftlfloorfrac{n+m}{k} ight floor-leftlfloorfrac{n}{k} ight floor-leftlfloorfrac{m}{k} ight floor=1)
否则，(leftlfloorfrac{n+m}{k} ight floor-leftlfloorfrac{n}{k} ight floor-leftlfloorfrac{m}{k} ight floor=0)
故把原式等价得写为(sumlimits_{k=1}^{n+m}varphi(k)leftlfloorfrac{n+m}{k} ight floor-sumlimits_{k=1}^{n}varphi(k)leftlfloorfrac{n}{k} ight floor-sumlimits_{k=1}^{m}varphi(k)leftlfloorfrac{m}{k} ight floor)
因为(sumlimits_{d|n}varphi(d)=n)
故化为(sumlimits_{k=1}^{n+m}k-sumlimits_{k=1}^{n}k-sumlimits_{k=1}^{m}k)