Задача М624‍‍

Найдите последовательность $(a_n)$‍,‍ определяемую условиями $a_1=1$‍,‍ $$ 1 + \sum_{d} (-1)^{n/d} a_{d} = 0, \tag{*} $$ где сумма $\sum$‍‍ берётся по всем делителям $d$‍‍ числа $n$‍‍ (включая $d=1$‍‍ и $d=n$‍).‍

Например, если $n=p$‍‍ — простое число, то (*) принимает вид $1 + (-1)^{p/1}a_1+(-1)^{p/p}a_p=0$‍,‍ откуда $a_p=2$‍,‍ если $p=2$‍,‍ и $a_p=0$‍‍ — если $p\gt 2$‍.‍