AtCoder Grand Contest 018 - A - Getting Difference

問題

A: Getting Difference - AtCoder Grand Contest 018 | AtCoder

解法

x=gcd(A[1], … A[n])とおく。 行う操作はgcdであることに気付けば、この操作で作れる数はxの倍数になることがわかる。 なので、各A[i]について何回かxを引いてKにできるか判定すればよい。

gist.github.com