全パターンを愚直に求めると$ O(K^N)で全く間に合わない gcdの結果がiになる物の数を求める これはKパターンしか無い gcdの結果がiになるのは配列の要素が全てiの倍数かつ2i,3i,...の倍数でないものがあること 全てiの倍数になる組み合わせは$ \left(\frac{k}{i}\right)^n通り これから$ \left(\frac{k}{2i}\right)^n, $ \…