>>365
Σ_(i=1,n) Σ_(d|gcd(k,x+i)) φ(d)
= Σ_(1≦i≦n, d|k, d|(x+i)) φ(d)
= Σ_(d|k) Σ(1≦i≦n, d|(x+i)) φ(d).

>>366
連続したd個の整数のうち少なくとも一つはdの倍数。
(x+1)から(x+n)までには、連続したd個の整数からなるブロックが[n/d]個あるから、
そのうちdの倍数も[n/d]個以上あることになる。