BOJ 26073 - 외로운 곰곰이는 친구가 있어요

BOJ 26073 - 외로운 곰곰이는 친구가 있어요

베주 항등식 날먹문제이다.

$$ a_1x_1+a_2x_2+\cdots+a_nx_n=k $$

의 해가 존재할 필요충분조건은 $gcd(a_1,a_2,\dots,a_n) \mid k$ 이기 때문에 이걸 각각 $\lvert x \rvert$와 $\lvert y \rvert$ 에 대해 검사만 해주면 된다.

void solve() {
   int n;
   cin >> n;
   for (int i = 0, x, y, k; i < n; i++) {
      cin >> x >> y >> k;
      vi move(k);
      fv(move);
      int g = 0;
      for (int i: move) g = gcd(g, i);
      if (abs(x) % g == 0 && abs(y) % g == 0) cout << "Ta-da\n";
      else cout << "Gave up\n";
   }
}