```
we can use Chinese Reminder Theorem (CRT) - https://en.wikipedia.org/wiki/Chinese_remainder_theorem
let's factorize n = p1^m1 \cdot p2^m2 \cdot ... \cdot pt^mt
(k-1) covers all numbers from 0 to (n-1)
prime powers are coprime
so according to CRT we can uniquely describe (k-1) by vector of remainders mod pi^mi for all i: (k-1) <-> [r1, r2, ..., rt], where ri = (k-1) mod (pi^mi)
then remainders for k will be [r1+1, r2+1, ..., rt+1], which means that k is not coprime with n if and only if for some i: (ri+1) mod pi = 0 <=> ri mod pi = (pi-1)
to calculate gcd(k-1,n) we will just take gcd(r1, p1^m1) \cdot gcd(r2, p2^m2) \cdot ... \cdot gcd(rt, pt^mt)
thus f(n) = \sum{[r1, r2, ..., rt]} (gcd(r1, p1^m1) * [r1 mod p1 != (p1-1)]) \cdot  (gcd(r2, p2^m2) * [r2 mod p2 != (p2-1)]) \cdot ... \cdot  (gcd(rt, pt^mt) * [rt mod pt != (pt-1)])
but that's the sum over all arrays with independent bounds for each ri of products of independent values for each ri
so we can rewrite it as
f(n) = \prod{i=1}^{t} \sum{ri=0}^{pi^mi-1} gcd(ri, pi^mi) * [ri mod pi != (pi-1)]
that means that f(n) is calculated as product of independently calculated values for each prime power, so it is multiplicative - https://en.wikipedia.org/wiki/Multiplicative_function
and actually f(n) = \prod{i=1}^{t} f(pi^mi)
now we only need to calculate it for prime powers
and we already have it written as a sum:
f(p^m) = \sum{r=0}^{p^m-1} gcd(r, p^m) * [r mod p != (p-1)]
gcd(r, p^m) is just p^w, where p^w is max power that divides r (or m if r=0)
group r by that power w
if r=0 the contribution is p^m
if 0<w<m the contribution is p^w * (p-1)p^{m-w-1} = (p-1) p^{m-1}
if w=0 we need to not consider r s.t. r mod p = (p-1), so the contribution is (p-2) p^{m-1}
summing that all up we will get (m+1) (p-1) p^{m-1}
that's already enough to solve the problem
to get the magical formula f(n) = d(n) phi(n) we just have to notice that d(n) and phi(n) are both multiplicative too
d(p^m) = (m+1)
phi(p^m) = (p-1) p^{m-1}
so it just happened that f(p^m) = d(p^m) phi(p^m)
```