口胡了一个题目，不会做：

求闭区间 $\left[1,k\right]$ 之间与 $n$ 互质整数的和。

（数据可能大一点？$n\leq10^6,k\leq10^9$？）

求解。