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

image.png

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

a1x1+a2x2+⋯+anxn=k a_1x_1+a_2x_2+\cdots+a_nx_n=k

의 해가 존재할 필요충분조건은 gcd(a1,a2,…,an)∣kgcd(a_1,a_2,\dots,a_n) \mid k 이기 때문에 이걸 각각 ∣x∣\lvert x \rvert와 ∣y∣\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";
   }
}

Tags:

Categories:

Updated:

Comments

You may also enjoy