---

Problem 531

---

Chinese leftovers

Let g(a,n,b,m) be the smallest non-negative solution x to the system:
x = a mod n
x = b mod m
if such a solution exists, otherwise 0.

E.g. g(2,4,4,6)=10, but g(3,4,4,6)=0.

Let φ(n) be Euler’s totient function.

Let f(n,m)=g(φ(n),n,φ(m),m).

Find ∑f(n,m) for 1000000 ≤ n < m < 1005000.

---

中国剩余定理

记g(a,n,b,m)为以下方程组的最小非负解：
x = a mod n
x = b mod m
如果解不存在，则该函数记为0。

例如，g(2,4,4,6)=10，但g(3,4,4,6)=0。

记φ(n)为欧拉总计函数。

记f(n,m)=g(φ(n),n,φ(m),m)。

对于1000000 ≤ n < m < 1005000，求∑f(n,m)。

---